sys/src/cmd/ndb/dn.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <ip.h>
   4 #include <ctype.h>
   5 #include "dns.h"
   6
   7 /*
   8  *  this comment used to say `our target is 4000 names cached, this should
   9  *  be larger on large servers'.  dns at Bell Labs starts off with
  10  *  about 1780 names.
  11  *
  12  * aging seems to corrupt the cache, so raise the trigger from 4000 until we
  13  * figure it out.
  14  */
  15 enum {
  16         /* these settings will trigger frequent aging */
  17         Deftarget       = 4000,
  18         Minage          =  5*Min,
  19         Defagefreq      = 15*Min,       /* age names this often (seconds) */
  20 };
  21
  22 /*
  23  *  Hash table for domain names.  The hash is based only on the
  24  *  first element of the domain name.
  25  */
  26 DN *ht[HTLEN];
  27
  28 static struct {
  29         Lock;
  30         ulong   names;          /* names allocated */
  31         ulong   oldest;         /* longest we'll leave a name around */
  32         int     active;
  33         int     mutex;
  34         ushort  id;             /* same size as in packet */
  35 } dnvars;
  36
  37 /* names of RR types */
  38 static char *rrtname[] =
  39 {
  40 [Ta]            "ip",
  41 [Tns]           "ns",
  42 [Tmd]           "md",
  43 [Tmf]           "mf",
  44 [Tcname]        "cname",
  45 [Tsoa]          "soa",
  46 [Tmb]           "mb",
  47 [Tmg]           "mg",
  48 [Tmr]           "mr",
  49 [Tnull]         "null",
  50 [Twks]          "wks",
  51 [Tptr]          "ptr",
  52 [Thinfo]        "hinfo",
  53 [Tminfo]        "minfo",
  54 [Tmx]           "mx",
  55 [Ttxt]          "txt",
  56 [Trp]           "rp",
  57 [Tafsdb]        "afsdb",
  58 [Tx25]          "x.25",
  59 [Tisdn]         "isdn",
  60 [Trt]           "rt",
  61 [Tnsap]         "nsap",
  62 [Tnsapptr]      "nsap-ptr",
  63 [Tsig]          "sig",
  64 [Tkey]          "key",
  65 [Tpx]           "px",
  66 [Tgpos]         "gpos",
  67 [Taaaa]         "ipv6",
  68 [Tloc]          "loc",
  69 [Tnxt]          "nxt",
  70 [Teid]          "eid",
  71 [Tnimloc]       "nimrod",
  72 [Tsrv]          "srv",
  73 [Tatma]         "atma",
  74 [Tnaptr]        "naptr",
  75 [Tkx]           "kx",
  76 [Tcert]         "cert",
  77 [Ta6]           "a6",
  78 [Tdname]        "dname",
  79 [Tsink]         "sink",
  80 [Topt]          "opt",
  81 [Tapl]          "apl",
  82 [Tds]           "ds",
  83 [Tsshfp]        "sshfp",
  84 [Tipseckey]     "ipseckey",
  85 [Trrsig]        "rrsig",
  86 [Tnsec]         "nsec",
  87 [Tdnskey]       "dnskey",
  88 [Tspf]          "spf",
  89 [Tuinfo]        "uinfo",
  90 [Tuid]          "uid",
  91 [Tgid]          "gid",
  92 [Tunspec]       "unspec",
  93 [Ttkey]         "tkey",
  94 [Ttsig]         "tsig",
  95 [Tixfr]         "ixfr",
  96 [Taxfr]         "axfr",
  97 [Tmailb]        "mailb",
  98 [Tmaila]        "maila",
  99 [Tall]          "all",
 100 [Tcaa]          "caa",
 101 };
 102
 103 /* names of response codes */
 104 char *rname[Rmask+1] =
 105 {
 106 [Rok]                   "ok",
 107 [Rformat]               "format error",
 108 [Rserver]               "server failure",
 109 [Rname]                 "bad name",
 110 [Runimplimented]        "unimplemented",
 111 [Rrefused]              "we don't like you",
 112 [Ryxdomain]             "name should not exist",
 113 [Ryxrrset]              "rr set should not exist",
 114 [Rnxrrset]              "rr set should exist",
 115 [Rnotauth]              "not authorative",
 116 [Rnotzone]              "not in zone",
 117 [Rbadvers]              "bad opt version",
 118 /* [Rbadsig]            "bad signature", */
 119 [Rbadkey]               "bad key",
 120 [Rbadtime]              "bad signature time",
 121 [Rbadmode]              "bad mode",
 122 [Rbadname]              "duplicate key name",
 123 [Rbadalg]               "bad algorithm",
 124 };
 125 unsigned nrname = nelem(rname);
 126
 127 /* names of op codes */
 128 char *opname[] =
 129 {
 130 [Oquery]        "query",
 131 [Oinverse]      "inverse query (retired)",
 132 [Ostatus]       "status",
 133 [Oupdate]       "update",
 134 };
 135
 136 ulong target = Deftarget;
 137 Lock    dnlock;
 138
 139 static ulong agefreq = Defagefreq;
 140
 141 static int rrequiv(RR *r1, RR *r2);
 142 static int sencodefmt(Fmt*);
 143
 144 static void
 145 ding(void*, char *msg)
 146 {
 147         if(strstr(msg, "alarm") != nil) {
 148                 stats.alarms++;
 149                 noted(NCONT);           /* resume with system call error */
 150         } else
 151                 noted(NDFLT);           /* die */
 152 }
 153
 154 void
 155 dninit(void)
 156 {
 157         fmtinstall('E', eipfmt);
 158         fmtinstall('I', eipfmt);
 159         fmtinstall('V', eipfmt);
 160         fmtinstall('R', rrfmt);
 161         fmtinstall('Q', rravfmt);
 162         fmtinstall('H', sencodefmt);
 163
 164         dnvars.oldest = maxage;
 165         dnvars.names = 0;
 166         dnvars.id = truerand(); /* don't start with same id every time */
 167
 168         notify(ding);
 169 }
 170
 171 /*
 172  *  hash for a domain name
 173  */
 174 static ulong
 175 dnhash(char *name)
 176 {
 177         ulong hash;
 178         uchar *val = (uchar*)name;
 179
 180         for(hash = 0; *val; val++)
 181                 hash = hash*13 + tolower(*val)-'a';
 182         return hash % HTLEN;
 183 }
 184
 185 /*
 186  *  lookup a symbol.  if enter is not zero and the name is
 187  *  not found, create it.
 188  */
 189 DN*
 190 dnlookup(char *name, int class, int enter)
 191 {
 192         DN **l;
 193         DN *dp;
 194
 195         l = &ht[dnhash(name)];
 196         lock(&dnlock);
 197         for(dp = *l; dp; dp = dp->next) {
 198                 assert(dp->magic == DNmagic);
 199                 if(dp->class == class && cistrcmp(dp->name, name) == 0){
 200                         dp->referenced = now;
 201                         unlock(&dnlock);
 202                         return dp;
 203                 }
 204                 l = &dp->next;
 205         }
 206
 207         if(!enter){
 208                 unlock(&dnlock);
 209                 return 0;
 210         }
 211         dnvars.names++;
 212         dp = emalloc(sizeof(*dp));
 213         dp->magic = DNmagic;
 214         dp->name = estrdup(name);
 215         dp->class = class;
 216         dp->rr = nil;
 217         dp->referenced = now;
 218         /* add new DN to tail of the hash list.  *l points to last next ptr. */
 219         dp->next = nil;
 220         *l = dp;
 221         unlock(&dnlock);
 222
 223         return dp;
 224 }
 225
 226 DN*
 227 idnlookup(char *name, int class, int enter)
 228 {
 229         char dom[Domlen];
 230
 231         if(utf2idn(name, dom, sizeof dom) >= 0)
 232                 name = dom;
 233         return dnlookup(name, class, enter);
 234 }
 235
 236 DN*
 237 ipalookup(uchar *ip, int class, int enter)
 238 {
 239         char addr[64];
 240
 241         snprint(addr, sizeof(addr), "%I", ip);
 242         return dnlookup(addr, class, enter);
 243 }
 244
 245 static int
 246 rrsame(RR *rr1, RR *rr2)
 247 {
 248         return rr1 == rr2 ||
 249                 rr1 != nil && rr2 != nil &&
 250                 rr1->db == rr2->db &&
 251                 rr1->auth == rr2->auth &&
 252                 rrequiv(rr1, rr2);
 253 }
 254
 255 static int
 256 rronlist(RR *rp, RR *lp)
 257 {
 258         for(; lp; lp = lp->next)
 259                 if (rrsame(lp, rp))
 260                         return 1;
 261         return 0;
 262 }
 263
 264 /*
 265  * dump the stats
 266  */
 267 void
 268 dnstats(char *file)
 269 {
 270         int i, fd;
 271
 272         fd = create(file, OWRITE, 0666);
 273         if(fd < 0)
 274                 return;
 275
 276         qlock(&stats);
 277         fprint(fd, "# system %s\n", sysname());
 278         fprint(fd, "# slave procs high-water mark\t%lud\n", stats.slavehiwat);
 279         fprint(fd, "# queries received by 9p\t%lud\n", stats.qrecvd9p);
 280         fprint(fd, "# queries received by udp\t%lud\n", stats.qrecvdudp);
 281         fprint(fd, "# queries answered from memory\t%lud\n", stats.answinmem);
 282         fprint(fd, "# queries sent by udp\t%lud\n", stats.qsent);
 283         for (i = 0; i < nelem(stats.under10ths); i++)
 284                 if (stats.under10ths[i] || i == nelem(stats.under10ths) - 1)
 285                         fprint(fd, "# responses arriving within %.1f s.\t%lud\n",
 286                                 (double)(i+1)/10, stats.under10ths[i]);
 287         fprint(fd, "\n# queries sent & timed-out\t%lud\n", stats.tmout);
 288         fprint(fd, "# cname queries timed-out\t%lud\n", stats.tmoutcname);
 289         fprint(fd, "# ipv6  queries timed-out\t%lud\n", stats.tmoutv6);
 290         fprint(fd, "\n# negative answers received\t%lud\n", stats.negans);
 291         fprint(fd, "# negative answers w Rserver set\t%lud\n", stats.negserver);
 292         fprint(fd, "# negative answers w bad delegation\t%lud\n",
 293                 stats.negbaddeleg);
 294         fprint(fd, "# negative answers w bad delegation & no answers\t%lud\n",
 295                 stats.negbdnoans);
 296         fprint(fd, "# negative answers w no Rname set\t%lud\n", stats.negnorname);
 297         fprint(fd, "# negative answers cached\t%lud\n", stats.negcached);
 298         qunlock(&stats);
 299
 300         lock(&dnlock);
 301         fprint(fd, "\n# domain names %lud target %lud\n", dnvars.names, target);
 302         unlock(&dnlock);
 303         close(fd);
 304 }
 305
 306 /*
 307  *  dump the cache
 308  */
 309 void
 310 dndump(char *file)
 311 {
 312         int i, fd;
 313         DN *dp;
 314         RR *rp;
 315
 316         fd = create(file, OWRITE, 0666);
 317         if(fd < 0)
 318                 return;
 319
 320         lock(&dnlock);
 321         for(i = 0; i < HTLEN; i++)
 322                 for(dp = ht[i]; dp; dp = dp->next){
 323                         fprint(fd, "%s\n", dp->name);
 324                         for(rp = dp->rr; rp; rp = rp->next) {
 325                                 fprint(fd, "\t%R %c%c %ld/%lud\n",
 326                                         rp, rp->auth? 'A': 'U',
 327                                         rp->db? 'D': 'N', (long)(rp->expire - now), rp->ttl);
 328                                 if (rronlist(rp, rp->next))
 329                                         fprint(fd, "*** duplicate:\n");
 330                         }
 331                 }
 332         unlock(&dnlock);
 333         close(fd);
 334 }
 335
 336 /*
 337  *  purge all records
 338  */
 339 void
 340 dnpurge(void)
 341 {
 342         DN *dp;
 343         RR *rp, *srp;
 344         int i;
 345
 346         lock(&dnlock);
 347
 348         for(i = 0; i < HTLEN; i++)
 349                 for(dp = ht[i]; dp; dp = dp->next){
 350                         srp = rp = dp->rr;
 351                         dp->rr = nil;
 352                         for(; rp != nil; rp = rp->next)
 353                                 rp->cached = 0;
 354                         rrfreelist(srp);
 355                 }
 356
 357         unlock(&dnlock);
 358 }
 359
 360 /*
 361  *  delete head of *l and free the old head.
 362  *  call with dnlock held.
 363  */
 364 static void
 365 rrdelhead(RR **l)
 366 {
 367         RR *rp;
 368
 369         if (canlock(&dnlock))
 370                 abort();        /* rrdelhead called with dnlock not held */
 371         rp = *l;
 372         if(rp == nil)
 373                 return;
 374         *l = rp->next;          /* unlink head */
 375         rp->cached = 0;         /* avoid blowing an assertion in rrfree */
 376         rrfree(rp);
 377 }
 378
 379 /*
 380  *  check the age of resource records, free any that have timed out.
 381  *  call with dnlock held.
 382  */
 383 void
 384 dnage(DN *dp)
 385 {
 386         RR **l, *rp;
 387         ulong diff;
 388
 389         if (canlock(&dnlock))
 390                 abort();        /* dnage called with dnlock not held */
 391         diff = now - dp->referenced;
 392         if(diff < Reserved || dp->mark != 0)
 393                 return;
 394
 395         l = &dp->rr;
 396         while ((rp = *l) != nil){
 397                 assert(rp->magic == RRmagic && rp->cached);
 398                 if(!rp->db && ((long)(rp->expire - now) <= 0 || diff > dnvars.oldest))
 399                         rrdelhead(l); /* rp == *l before; *l == rp->next after */
 400                 else
 401                         l = &rp->next;
 402         }
 403 }
 404
 405 #define MARK(dp)        { if (dp) (dp)->mark |= 2; }
 406
 407 /* mark a domain name and those in its RRs as never to be aged */
 408 void
 409 dnagenever(DN *dp)
 410 {
 411         RR *rp;
 412
 413         lock(&dnlock);
 414
 415         /* mark all referenced domain names */
 416         MARK(dp);
 417         for(rp = dp->rr; rp; rp = rp->next){
 418                 MARK(rp->owner);
 419                 if(rp->negative){
 420                         MARK(rp->negsoaowner);
 421                         continue;
 422                 }
 423                 switch(rp->type){
 424                 case Thinfo:
 425                         MARK(rp->cpu);
 426                         MARK(rp->os);
 427                         break;
 428                 case Ttxt:
 429                         break;
 430                 case Tcname:
 431                 case Tmb:
 432                 case Tmd:
 433                 case Tmf:
 434                 case Tns:
 435                 case Tmx:
 436                 case Tsrv:
 437                         MARK(rp->host);
 438                         break;
 439                 case Tmg:
 440                 case Tmr:
 441                         MARK(rp->mb);
 442                         break;
 443                 case Tminfo:
 444                         MARK(rp->rmb);
 445                         MARK(rp->mb);
 446                         break;
 447                 case Trp:
 448                         MARK(rp->rmb);
 449                         MARK(rp->rp);
 450                         break;
 451                 case Ta:
 452                 case Taaaa:
 453                         MARK(rp->ip);
 454                         break;
 455                 case Tptr:
 456                         MARK(rp->ptr);
 457                         break;
 458                 case Tsoa:
 459                         MARK(rp->host);
 460                         MARK(rp->rmb);
 461                         break;
 462                 case Tsig:
 463                         MARK(rp->sig->signer);
 464                         break;
 465                 case Tcaa:
 466                         MARK(rp->caa->tag);
 467                         break;
 468                 }
 469         }
 470
 471         unlock(&dnlock);
 472 }
 473
 474 #define REF(dp) { if (dp) (dp)->mark |= 1; }
 475
 476 /*
 477  *  periodicly sweep for old records and remove unreferenced domain names
 478  *
 479  *  only called when all other threads are locked out
 480  */
 481 void
 482 dnageall(int doit)
 483 {
 484         DN *dp, **l;
 485         int i;
 486         RR *rp;
 487         static ulong nextage;
 488
 489         if(dnvars.names < target || ((long)(nextage - now) > 0 && !doit)){
 490                 dnvars.oldest = maxage;
 491                 return;
 492         }
 493
 494         if(dnvars.names >= target) {
 495                 dnslog("more names (%lud) than target (%lud)", dnvars.names,
 496                         target);
 497                 dnvars.oldest /= 2;
 498                 if (dnvars.oldest < Minage)
 499                         dnvars.oldest = Minage;         /* don't be silly */
 500         }
 501         if (agefreq > dnvars.oldest / 2)
 502                 nextage = now + dnvars.oldest / 2;
 503         else
 504                 nextage = now + (ulong)agefreq;
 505
 506         lock(&dnlock);
 507
 508         /* time out all old entries (and set refs to 0) */
 509         for(i = 0; i < HTLEN; i++)
 510                 for(dp = ht[i]; dp; dp = dp->next){
 511                         dp->mark &= ~1;
 512                         dnage(dp);
 513                 }
 514
 515         /* mark all referenced domain names */
 516         for(i = 0; i < HTLEN; i++)
 517                 for(dp = ht[i]; dp; dp = dp->next)
 518                         for(rp = dp->rr; rp; rp = rp->next){
 519                                 REF(rp->owner);
 520                                 if(rp->negative){
 521                                         REF(rp->negsoaowner);
 522                                         continue;
 523                                 }
 524                                 switch(rp->type){
 525                                 case Thinfo:
 526                                         REF(rp->cpu);
 527                                         REF(rp->os);
 528                                         break;
 529                                 case Ttxt:
 530                                         break;
 531                                 case Tcname:
 532                                 case Tmb:
 533                                 case Tmd:
 534                                 case Tmf:
 535                                 case Tns:
 536                                 case Tmx:
 537                                 case Tsrv:
 538                                         REF(rp->host);
 539                                         break;
 540                                 case Tmg:
 541                                 case Tmr:
 542                                         REF(rp->mb);
 543                                         break;
 544                                 case Tminfo:
 545                                         REF(rp->rmb);
 546                                         REF(rp->mb);
 547                                         break;
 548                                 case Trp:
 549                                         REF(rp->rmb);
 550                                         REF(rp->rp);
 551                                         break;
 552                                 case Ta:
 553                                 case Taaaa:
 554                                         REF(rp->ip);
 555                                         break;
 556                                 case Tptr:
 557                                         REF(rp->ptr);
 558                                         break;
 559                                 case Tsoa:
 560                                         REF(rp->host);
 561                                         REF(rp->rmb);
 562                                         break;
 563                                 case Tsig:
 564                                         REF(rp->sig->signer);
 565                                         break;
 566                                 }
 567                         }
 568
 569         /* sweep and remove unreferenced domain names */
 570         for(i = 0; i < HTLEN; i++){
 571                 l = &ht[i];
 572                 for(dp = *l; dp; dp = *l){
 573                         if(dp->rr == nil && dp->mark == 0){
 574                                 assert(dp->magic == DNmagic);
 575                                 *l = dp->next;
 576
 577                                 free(dp->name);
 578                                 memset(dp, 0, sizeof *dp); /* cause trouble */
 579                                 dp->magic = ~DNmagic;
 580                                 free(dp);
 581
 582                                 dnvars.names--;
 583                                 continue;
 584                         }
 585                         l = &dp->next;
 586                 }
 587         }
 588
 589         unlock(&dnlock);
 590 }
 591
 592 /*
 593  *  timeout all database records (used when rereading db)
 594  */
 595 void
 596 dnagedb(void)
 597 {
 598         DN *dp;
 599         int i;
 600         RR *rp;
 601
 602         lock(&dnlock);
 603
 604         /* time out all database entries */
 605         for(i = 0; i < HTLEN; i++)
 606                 for(dp = ht[i]; dp; dp = dp->next) {
 607                         dp->mark = 0;
 608                         for(rp = dp->rr; rp; rp = rp->next)
 609                                 if(rp->db)
 610                                         rp->expire = 0;
 611                 }
 612
 613         unlock(&dnlock);
 614 }
 615
 616 /*
 617  *  mark all local db records about my area as authoritative,
 618  *  delete timed out ones
 619  */
 620 void
 621 dnauthdb(void)
 622 {
 623         int i;
 624         ulong minttl;
 625         Area *area;
 626         DN *dp;
 627         RR *rp, **l;
 628
 629         lock(&dnlock);
 630
 631         /* time out all database entries */
 632         for(i = 0; i < HTLEN; i++)
 633                 for(dp = ht[i]; dp; dp = dp->next){
 634                         area = inmyarea(dp->name);
 635                         l = &dp->rr;
 636                         for(rp = *l; rp; rp = *l){
 637                                 if(rp->db){
 638                                         if(rp->expire == 0){
 639                                                 rrdelhead(l);
 640                                                 continue;
 641                                         }
 642                                         if(area){
 643                                                 minttl = area->soarr->soa->minttl;
 644                                                 if(rp->ttl < minttl)
 645                                                         rp->ttl = minttl;
 646                                                 rp->auth = 1;
 647                                         } else if(rp->type == Tns && inmyarea(rp->host->name))
 648                                                 rp->auth = 1;
 649                                 }
 650                                 l = &rp->next;
 651                         }
 652                 }
 653
 654         unlock(&dnlock);
 655 }
 656
 657 /*
 658  *  keep track of other processes to know if we can
 659  *  garbage collect.  block while garbage collecting.
 660  */
 661 int
 662 getactivity(Request *req, int recursive)
 663 {
 664         int rv;
 665
 666         if(traceactivity)
 667                 dnslog("get: %d active by pid %d from %p",
 668                         dnvars.active, getpid(), getcallerpc(&req));
 669         lock(&dnvars);
 670         /*
 671          * can't block here if we're already holding one
 672          * of the dnvars.active (recursive).  will deadlock.
 673          */
 674         while(!recursive && dnvars.mutex){
 675                 unlock(&dnvars);
 676                 sleep(100);                     /* tune; was 200 */
 677                 lock(&dnvars);
 678         }
 679         rv = ++dnvars.active;
 680         now = time(nil);
 681         nowns = nsec();
 682         req->id = ++dnvars.id;
 683         req->aux = nil;
 684         unlock(&dnvars);
 685
 686         return rv;
 687 }
 688 void
 689 putactivity(int recursive)
 690 {
 691         if(traceactivity)
 692                 dnslog("put: %d active by pid %d",
 693                         dnvars.active, getpid());
 694         lock(&dnvars);
 695         dnvars.active--;
 696         assert(dnvars.active >= 0); /* "dnvars.active %d", dnvars.active */
 697
 698         /*
 699          *  clean out old entries and check for new db periodicly
 700          *  can't block here if being called to let go a "recursive" lock
 701          *  or we'll deadlock waiting for ourselves to give up the dnvars.active.
 702          */
 703         if (recursive || dnvars.mutex ||
 704             (needrefresh == 0 && dnvars.active > 0)){
 705                 unlock(&dnvars);
 706                 return;
 707         }
 708
 709         /* wait till we're alone */
 710         dnvars.mutex = 1;
 711         while(dnvars.active > 0){
 712                 unlock(&dnvars);
 713                 sleep(100);             /* tune; was 100 */
 714                 lock(&dnvars);
 715         }
 716         unlock(&dnvars);
 717
 718         db2cache(needrefresh);
 719
 720         dnageall(0);
 721
 722         /* let others back in */
 723         needrefresh = 0;
 724         dnvars.mutex = 0;
 725 }
 726
 727 int
 728 rrlistlen(RR *rp)
 729 {
 730         int n;
 731
 732         n = 0;
 733         for(; rp; rp = rp->next)
 734                 ++n;
 735         return n;
 736 }
 737
 738 /*
 739  *  Attach a single resource record to a domain name (new->owner).
 740  *      - Avoid duplicates with already present RR's
 741  *      - Chain all RR's of the same type adjacent to one another
 742  *      - chain authoritative RR's ahead of non-authoritative ones
 743  *      - remove any expired RR's
 744  *  If new is a stale duplicate, rrfree it.
 745  *  Must be called with dnlock held.
 746  */
 747 static void
 748 rrattach1(RR *new, int auth)
 749 {
 750         RR **l;
 751         RR *rp;
 752         DN *dp;
 753         ulong ttl;
 754
 755         assert(new->magic == RRmagic && !new->cached);
 756
 757         dp = new->owner;
 758         assert(dp != nil && dp->magic == DNmagic);
 759         new->auth |= auth;
 760         new->next = 0;
 761
 762         /*
 763          * try not to let responses expire before we
 764          * can use them to complete this query, by extending
 765          * past (or nearly past) expiration time.
 766          */
 767         if(new->db)
 768                 ttl = Year;
 769         else
 770                 ttl = new->ttl;
 771         if(ttl <= Min)
 772                 ttl = 10*Min;
 773         new->expire = now + ttl;
 774
 775         /*
 776          *  find first rr of the right type
 777          */
 778         l = &dp->rr;
 779         for(rp = *l; rp; rp = *l){
 780                 assert(rp->magic == RRmagic && rp->cached);
 781                 if(rp->type == new->type)
 782                         break;
 783                 l = &rp->next;
 784         }
 785
 786         /*
 787          *  negative entries replace positive entries
 788          *  positive entries replace negative entries
 789          *  newer entries replace older entries with the same fields
 790          *
 791          *  look farther ahead than just the next entry when looking
 792          *  for duplicates; RRs of a given type can have different rdata
 793          *  fields (e.g. multiple NS servers).
 794          */
 795         while ((rp = *l) != nil){
 796                 assert(rp->magic == RRmagic && rp->cached);
 797                 if(rp->type != new->type)
 798                         break;
 799
 800                 if(rp->db == new->db && rp->auth == new->auth){
 801                         /* negative drives out positive and vice versa */
 802                         if(rp->negative != new->negative) {
 803                                 /* rp == *l before; *l == rp->next after */
 804                                 rrdelhead(l);
 805                                 continue;
 806                         }
 807                         /* all things equal, pick the newer one */
 808                         else if(rrequiv(rp, new)){
 809                                 /* old drives out new */
 810                                 if((long)(rp->expire - new->expire) > 0) {
 811                                         rrfree(new);
 812                                         return;
 813                                 }
 814                                 /* rp == *l before; *l == rp->next after */
 815                                 rrdelhead(l);
 816                                 continue;
 817                         }
 818                         /*
 819                          *  Hack for pointer records.  This makes sure
 820                          *  the ordering in the list reflects the ordering
 821                          *  received or read from the database
 822                          */
 823                         else if(rp->type == Tptr &&
 824                             !rp->negative && !new->negative &&
 825                             rp->ptr->ordinal > new->ptr->ordinal)
 826                                 break;
 827                 }
 828                 l = &rp->next;
 829         }
 830
 831         if (rronlist(new, rp)) {
 832                 /* should not happen; duplicates were processed above */
 833                 dnslog("adding duplicate %R to list of %R; aborting", new, rp);
 834                 abort();
 835         }
 836         /*
 837          *  add to chain
 838          */
 839         new->cached = 1;
 840         new->next = rp;
 841         *l = new;
 842 }
 843
 844 /*
 845  *  Attach a list of resource records to a domain name.
 846  *  May rrfree any stale duplicate RRs; dismembers the list.
 847  *  Upon return, every RR in the list will have been rrfree-d
 848  *  or attached to its domain name.
 849  *  See rrattach1 for properties preserved.
 850  */
 851 void
 852 rrattach(RR *rp, int auth)
 853 {
 854         RR *next;
 855         DN *dp;
 856
 857         lock(&dnlock);
 858         for(; rp; rp = next){
 859                 next = rp->next;
 860                 rp->next = nil;
 861                 dp = rp->owner;
 862                 /* avoid any outside spoofing */
 863                 if(cfg.cachedb && !rp->db && inmyarea(dp->name))
 864                         rrfree(rp);
 865                 else
 866                         rrattach1(rp, auth);
 867         }
 868         unlock(&dnlock);
 869 }
 870
 871 RR**
 872 rrcopy(RR *rp, RR **last)
 873 {
 874         RR *nrp;
 875         SOA *soa;
 876         Srv *srv;
 877         Key *key;
 878         Caa *caa;
 879         Cert *cert;
 880         Sig *sig;
 881         Null *null;
 882         Txt *t, *nt, **l;
 883
 884         assert(rp->magic == RRmagic);
 885         nrp = rralloc(rp->type);
 886         switch(rp->type){
 887         case Tsoa:
 888                 soa = nrp->soa;
 889                 *nrp = *rp;
 890                 nrp->soa = soa;
 891                 *soa = *rp->soa;
 892                 soa->slaves = copyserverlist(rp->soa->slaves);
 893                 break;
 894         case Tsrv:
 895                 srv = nrp->srv;
 896                 *nrp = *rp;
 897                 nrp->srv = srv;
 898                 *srv = *rp->srv;
 899                 break;
 900         case Tdnskey:
 901         case Tkey:
 902                 key = nrp->key;
 903                 *nrp = *rp;
 904                 nrp->key = key;
 905                 *key = *rp->key;
 906                 key->data = emalloc(key->dlen);
 907                 memmove(key->data, rp->key->data, rp->key->dlen);
 908                 break;
 909         case Tcaa:
 910                 caa = nrp->caa;
 911                 *nrp = *rp;
 912                 nrp->caa = caa;
 913                 *caa = *rp->caa;
 914                 caa->data = emalloc(caa->dlen);
 915                 memmove(caa->data, rp->caa->data, rp->caa->dlen);
 916                 break;
 917         case Tcert:
 918                 cert = nrp->cert;
 919                 *nrp = *rp;
 920                 nrp->cert = cert;
 921                 *cert = *rp->cert;
 922                 cert->data = emalloc(cert->dlen);
 923                 memmove(cert->data, rp->cert->data, rp->cert->dlen);
 924                 break;
 925         case Tsig:
 926                 sig = nrp->sig;
 927                 *nrp = *rp;
 928                 nrp->sig = sig;
 929                 *sig = *rp->sig;
 930                 sig->data = emalloc(sig->dlen);
 931                 memmove(sig->data, rp->sig->data, rp->sig->dlen);
 932                 break;
 933         case Tnull:
 934                 null = nrp->null;
 935                 *nrp = *rp;
 936                 nrp->null = null;
 937                 *null = *rp->null;
 938                 null->data = emalloc(null->dlen);
 939                 memmove(null->data, rp->null->data, rp->null->dlen);
 940                 break;
 941         case Ttxt:
 942                 *nrp = *rp;
 943                 l = &nrp->txt;
 944                 *l = nil;
 945                 for(t = rp->txt; t != nil; t = t->next){
 946                         nt = emalloc(sizeof(*nt));
 947                         nt->p = estrdup(t->p);
 948                         nt->next = nil;
 949                         *l = nt;
 950                         l = &nt->next;
 951                 }
 952                 break;
 953         default:
 954                 *nrp = *rp;
 955                 break;
 956         }
 957         nrp->pc = getcallerpc(&rp);
 958         setmalloctag(nrp, nrp->pc);
 959         nrp->cached = 0;
 960         nrp->next = nil;
 961         *last = nrp;
 962         return &nrp->next;
 963 }
 964
 965 /*
 966  *  lookup a resource record of a particular type and
 967  *  class attached to a domain name.  Return copies.
 968  *
 969  *  Priority ordering is:
 970  *      db authoritative
 971  *      not timed out network authoritative
 972  *      not timed out network unauthoritative
 973  *      unauthoritative db
 974  *
 975  *  if flag NOneg is set, don't return negative cached entries.
 976  *  return nothing instead.
 977  */
 978 RR*
 979 rrlookup(DN *dp, int type, int flag)
 980 {
 981         RR *rp, *first, **last;
 982
 983         assert(dp->magic == DNmagic);
 984
 985         first = nil;
 986         last = &first;
 987         lock(&dnlock);
 988
 989         /* try for an authoritative db entry */
 990         for(rp = dp->rr; rp; rp = rp->next){
 991                 assert(rp->magic == RRmagic && rp->cached);
 992                 if(rp->db)
 993                 if(rp->auth)
 994                 if(tsame(type, rp->type))
 995                         last = rrcopy(rp, last);
 996         }
 997         if(first)
 998                 goto out;
 999
1000         /* try for a living authoritative network entry */
1001         for(rp = dp->rr; rp; rp = rp->next){
1002                 if(!rp->db)
1003                 if(rp->auth)
1004                 if((long)(rp->expire - now) > 0)
1005                 if(tsame(type, rp->type)){
1006                         if(flag == NOneg && rp->negative)
1007                                 goto out;
1008                         last = rrcopy(rp, last);
1009                 }
1010         }
1011         if(first)
1012                 goto out;
1013
1014         /* try for a living unauthoritative network entry */
1015         for(rp = dp->rr; rp; rp = rp->next){
1016                 if(!rp->db)
1017                 if((long)(rp->expire - now) > 0)
1018                 if(tsame(type, rp->type)){
1019                         if(flag == NOneg && rp->negative)
1020                                 goto out;
1021                         last = rrcopy(rp, last);
1022                 }
1023         }
1024         if(first)
1025                 goto out;
1026
1027         /* try for an unauthoritative db entry */
1028         for(rp = dp->rr; rp; rp = rp->next){
1029                 if(rp->db)
1030                 if(tsame(type, rp->type))
1031                         last = rrcopy(rp, last);
1032         }
1033         if(first)
1034                 goto out;
1035
1036         /* otherwise, settle for anything we got (except for negative caches) */
1037         for(rp = dp->rr; rp; rp = rp->next)
1038                 if(tsame(type, rp->type)){
1039                         if(rp->negative)
1040                                 goto out;
1041                         last = rrcopy(rp, last);
1042                 }
1043
1044 out:
1045         unlock(&dnlock);
1046         unique(first);
1047         return first;
1048 }
1049
1050 /*
1051  *  convert an ascii RR type name to its integer representation
1052  */
1053 int
1054 rrtype(char *atype)
1055 {
1056         int i;
1057
1058         for(i = 0; i < nelem(rrtname); i++)
1059                 if(rrtname[i] && strcmp(rrtname[i], atype) == 0)
1060                         return i;
1061
1062         /* make any a synonym for all */
1063         if(strcmp(atype, "any") == 0)
1064                 return Tall;
1065         else if(isascii(atype[0]) && isdigit(atype[0]))
1066                 return atoi(atype);
1067         else
1068                 return -1;
1069 }
1070
1071 /*
1072  *  return 0 if not a supported rr type
1073  */
1074 int
1075 rrsupported(int type)
1076 {
1077         if(type < 0 || type >= nelem(rrtname))
1078                 return 0;
1079         return rrtname[type] != nil;
1080 }
1081
1082 /*
1083  *  compare 2 types
1084  */
1085 int
1086 tsame(int t1, int t2)
1087 {
1088         return t1 == t2 || t1 == Tall;
1089 }
1090
1091 /*
1092  *  Add resource records to a list.
1093  */
1094 RR*
1095 rrcat(RR **start, RR *rp)
1096 {
1097         RR *olp, *nlp;
1098         RR **last;
1099
1100         /* check for duplicates */
1101         for (olp = *start; 0 && olp; olp = olp->next)
1102                 for (nlp = rp; nlp; nlp = nlp->next)
1103                         if (rrsame(nlp, olp))
1104                                 dnslog("rrcat: duplicate RR: %R", nlp);
1105         USED(olp);
1106
1107         last = start;
1108         while(*last != nil)
1109                 last = &(*last)->next;
1110
1111         *last = rp;
1112         return *start;
1113 }
1114
1115 RR*
1116 rrremfilter(RR **l, int (*filter)(RR*, void*), void *arg)
1117 {
1118         RR *first, *rp;
1119         RR **nl;
1120
1121         first = nil;
1122         nl = &first;
1123         while(*l != nil){
1124                 rp = *l;
1125                 if((*filter)(rp, arg)){
1126                         *l = rp->next;
1127                         *nl = rp;
1128                         nl = &rp->next;
1129                         *nl = nil;
1130                 } else
1131                         l = &(*l)->next;
1132         }
1133
1134         return first;
1135 }
1136
1137 static int
1138 filterneg(RR *rp, void*)
1139 {
1140         return rp->negative;
1141 }
1142 static int
1143 filtertype(RR *rp, void *arg)
1144 {
1145         return rp->type == *((int*)arg);
1146 }
1147 static int
1148 filterowner(RR *rp, void *arg)
1149 {
1150         return rp->owner == (DN*)arg;
1151 }
1152
1153 /*
1154  *  remove negative cache rr's from an rr list
1155  */
1156 RR*
1157 rrremneg(RR **l)
1158 {
1159         return rrremfilter(l, filterneg, nil);
1160 }
1161
1162 /*
1163  *  remove rr's of a particular type from an rr list
1164  */
1165 RR*
1166 rrremtype(RR **l, int type)
1167 {
1168         return rrremfilter(l, filtertype, &type);
1169 }
1170
1171 /*
1172  *  remove rr's of a particular owner from an rr list
1173  */
1174 RR*
1175 rrremowner(RR **l, DN *owner)
1176 {
1177         return rrremfilter(l, filterowner, owner);
1178 }
1179
1180 static char *
1181 dnname(DN *dn)
1182 {
1183         return dn? dn->name: "<null>";
1184 }
1185
1186 static char *
1187 idnname(DN *dn, char *buf, int nbuf)
1188 {
1189         char *name;
1190
1191         name = dnname(dn);
1192         if(idn2utf(name, buf, nbuf) >= 0)
1193                 return buf;
1194         return name;
1195 }
1196
1197 /*
1198  *  print conversion for rr records
1199  */
1200 int
1201 rrfmt(Fmt *f)
1202 {
1203         int rv;
1204         char *strp;
1205         char buf[Domlen];
1206         Fmt fstr;
1207         RR *rp;
1208         Server *s;
1209         SOA *soa;
1210         Srv *srv;
1211         Txt *t;
1212
1213         fmtstrinit(&fstr);
1214
1215         rp = va_arg(f->args, RR*);
1216         if(rp == nil){
1217                 fmtprint(&fstr, "<null>");
1218                 goto out;
1219         }
1220
1221         fmtprint(&fstr, "%s %s", dnname(rp->owner),
1222                 rrname(rp->type, buf, sizeof buf));
1223
1224         if(rp->negative){
1225                 fmtprint(&fstr, "\tnegative - rcode %d", rp->negrcode);
1226                 goto out;
1227         }
1228
1229         switch(rp->type){
1230         case Thinfo:
1231                 fmtprint(&fstr, "\t%s %s", dnname(rp->cpu), dnname(rp->os));
1232                 break;
1233         case Tcname:
1234         case Tmb:
1235         case Tmd:
1236         case Tmf:
1237         case Tns:
1238                 fmtprint(&fstr, "\t%s", dnname(rp->host));
1239                 break;
1240         case Tmg:
1241         case Tmr:
1242                 fmtprint(&fstr, "\t%s", dnname(rp->mb));
1243                 break;
1244         case Tminfo:
1245                 fmtprint(&fstr, "\t%s %s", dnname(rp->mb), dnname(rp->rmb));
1246                 break;
1247         case Tmx:
1248                 fmtprint(&fstr, "\t%lud %s", rp->pref, dnname(rp->host));
1249                 break;
1250         case Ta:
1251         case Taaaa:
1252                 fmtprint(&fstr, "\t%s", dnname(rp->ip));
1253                 break;
1254         case Tptr:
1255                 fmtprint(&fstr, "\t%s", dnname(rp->ptr));
1256                 break;
1257         case Tsoa:
1258                 soa = rp->soa;
1259                 fmtprint(&fstr, "\t%s %s %lud %lud %lud %lud %lud",
1260                         dnname(rp->host), dnname(rp->rmb),
1261                         (soa? soa->serial: 0),
1262                         (soa? soa->refresh: 0), (soa? soa->retry: 0),
1263                         (soa? soa->expire: 0), (soa? soa->minttl: 0));
1264                 if (soa)
1265                         for(s = soa->slaves; s != nil; s = s->next)
1266                                 fmtprint(&fstr, " %s", s->name);
1267                 break;
1268         case Tsrv:
1269                 srv = rp->srv;
1270                 fmtprint(&fstr, "\t%ud %ud %ud %s",
1271                         (srv? srv->pri: 0), (srv? srv->weight: 0),
1272                         rp->port, dnname(rp->host));
1273                 break;
1274         case Tnull:
1275                 if (rp->null == nil)
1276                         fmtprint(&fstr, "\t<null>");
1277                 else
1278                         fmtprint(&fstr, "\t%.*H", rp->null->dlen,
1279                                 rp->null->data);
1280                 break;
1281         case Ttxt:
1282                 fmtprint(&fstr, "\t");
1283                 for(t = rp->txt; t != nil; t = t->next)
1284                         fmtprint(&fstr, "%s", t->p);
1285                 break;
1286         case Trp:
1287                 fmtprint(&fstr, "\t%s %s", dnname(rp->rmb), dnname(rp->rp));
1288                 break;
1289         case Tdnskey:
1290         case Tkey:
1291                 if (rp->key == nil)
1292                         fmtprint(&fstr, "\t<null> <null> <null>");
1293                 else
1294                         fmtprint(&fstr, "\t%d %d %d", rp->key->flags,
1295                                 rp->key->proto, rp->key->alg);
1296                 break;
1297         case Tsig:
1298                 if (rp->sig == nil)
1299                         fmtprint(&fstr,
1300                    "\t<null> <null> <null> <null> <null> <null> <null> <null>");
1301                 else
1302                         fmtprint(&fstr, "\t%d %d %d %lud %lud %lud %d %s",
1303                                 rp->sig->type, rp->sig->alg, rp->sig->labels,
1304                                 rp->sig->ttl, rp->sig->exp, rp->sig->incep,
1305                                 rp->sig->tag, dnname(rp->sig->signer));
1306                 break;
1307         case Tcert:
1308                 if (rp->cert == nil)
1309                         fmtprint(&fstr, "\t<null> <null> <null>");
1310                 else
1311                         fmtprint(&fstr, "\t%d %d %d",
1312                                 rp->cert->type, rp->cert->tag, rp->cert->alg);
1313                 break;
1314         case Tcaa:
1315                 if (rp->caa == nil)
1316                         fmtprint(&fstr, "\t<null> <null> <null>");
1317                 else
1318                         fmtprint(&fstr, "\t%d %s %.*s",
1319                                 rp->caa->flags, dnname(rp->caa->tag),
1320                                 rp->caa->dlen, (char*)rp->caa->data);
1321                 break;
1322         }
1323 out:
1324         strp = fmtstrflush(&fstr);
1325         rv = fmtstrcpy(f, strp);
1326         free(strp);
1327         return rv;
1328 }
1329
1330 /*
1331  *  print conversion for rr records in attribute value form
1332  */
1333 int
1334 rravfmt(Fmt *f)
1335 {
1336         int rv, quote;
1337         char buf[Domlen], *strp;
1338         Fmt fstr;
1339         RR *rp;
1340         Server *s;
1341         SOA *soa;
1342         Srv *srv;
1343         Txt *t;
1344
1345         fmtstrinit(&fstr);
1346
1347         rp = va_arg(f->args, RR*);
1348         if(rp == nil){
1349                 fmtprint(&fstr, "<null>");
1350                 goto out;
1351         }
1352
1353         if(rp->type == Tptr)
1354                 fmtprint(&fstr, "ptr=%s", dnname(rp->owner));
1355         else
1356                 fmtprint(&fstr, "dom=%s", idnname(rp->owner, buf, sizeof(buf)));
1357
1358         switch(rp->type){
1359         case Thinfo:
1360                 fmtprint(&fstr, " cpu=%s os=%s",
1361                         idnname(rp->cpu, buf, sizeof(buf)),
1362                         idnname(rp->os, buf, sizeof(buf)));
1363                 break;
1364         case Tcname:
1365                 fmtprint(&fstr, " cname=%s", idnname(rp->host, buf, sizeof(buf)));
1366                 break;
1367         case Tmb:
1368         case Tmd:
1369         case Tmf:
1370                 fmtprint(&fstr, " mbox=%s", idnname(rp->host, buf, sizeof(buf)));
1371                 break;
1372         case Tns:
1373                 fmtprint(&fstr,  " ns=%s", idnname(rp->host, buf, sizeof(buf)));
1374                 break;
1375         case Tmg:
1376         case Tmr:
1377                 fmtprint(&fstr, " mbox=%s", idnname(rp->mb, buf, sizeof(buf)));
1378                 break;
1379         case Tminfo:
1380                 fmtprint(&fstr, " mbox=%s mbox=%s",
1381                         idnname(rp->mb, buf, sizeof(buf)),
1382                         idnname(rp->rmb, buf, sizeof(buf)));
1383                 break;
1384         case Tmx:
1385                 fmtprint(&fstr, " pref=%lud mx=%s", rp->pref,
1386                         idnname(rp->host, buf, sizeof(buf)));
1387                 break;
1388         case Ta:
1389         case Taaaa:
1390                 fmtprint(&fstr, " ip=%s", dnname(rp->ip));
1391                 break;
1392         case Tptr:
1393                 fmtprint(&fstr, " dom=%s", dnname(rp->ptr));
1394                 break;
1395         case Tsoa:
1396                 soa = rp->soa;
1397                 fmtprint(&fstr,
1398 " ns=%s mbox=%s serial=%lud refresh=%lud retry=%lud expire=%lud ttl=%lud",
1399                         idnname(rp->host, buf, sizeof(buf)),
1400                         idnname(rp->rmb, buf, sizeof(buf)),
1401                         (soa? soa->serial: 0),
1402                         (soa? soa->refresh: 0), (soa? soa->retry: 0),
1403                         (soa? soa->expire: 0), (soa? soa->minttl: 0));
1404                 for(s = soa->slaves; s != nil; s = s->next)
1405                         fmtprint(&fstr, " dnsslave=%s", s->name);
1406                 break;
1407         case Tsrv:
1408                 srv = rp->srv;
1409                 fmtprint(&fstr, " pri=%ud weight=%ud port=%ud target=%s",
1410                         (srv? srv->pri: 0), (srv? srv->weight: 0),
1411                         rp->port, idnname(rp->host, buf, sizeof(buf)));
1412                 break;
1413         case Tnull:
1414                 if (rp->null == nil)
1415                         fmtprint(&fstr, " null=<null>");
1416                 else
1417                         fmtprint(&fstr, " null=%.*H", rp->null->dlen,
1418                                 rp->null->data);
1419                 break;
1420         case Ttxt:
1421                 fmtprint(&fstr, " txt=");
1422                 quote = 0;
1423                 for(t = rp->txt; t != nil; t = t->next)
1424                         if(strchr(t->p, ' '))
1425                                 quote = 1;
1426                 if(quote)
1427                         fmtprint(&fstr, "\"");
1428                 for(t = rp->txt; t != nil; t = t->next)
1429                         fmtprint(&fstr, "%s", t->p);
1430                 if(quote)
1431                         fmtprint(&fstr, "\"");
1432                 break;
1433         case Trp:
1434                 fmtprint(&fstr, " rp=%s txt=%s",
1435                         idnname(rp->rmb, buf, sizeof(buf)),
1436                         idnname(rp->rp, buf, sizeof(buf)));
1437                 break;
1438         case Tdnskey:
1439         case Tkey:
1440                 if (rp->key == nil)
1441                         fmtprint(&fstr, " flags=<null> proto=<null> alg=<null>");
1442                 else
1443                         fmtprint(&fstr, " flags=%d proto=%d alg=%d",
1444                                 rp->key->flags, rp->key->proto, rp->key->alg);
1445                 break;
1446         case Tsig:
1447                 if (rp->sig == nil)
1448                         fmtprint(&fstr,
1449 " type=<null> alg=<null> labels=<null> ttl=<null> exp=<null> incep=<null> tag=<null> signer=<null>");
1450                 else
1451                         fmtprint(&fstr,
1452 " type=%d alg=%d labels=%d ttl=%lud exp=%lud incep=%lud tag=%d signer=%s",
1453                                 rp->sig->type, rp->sig->alg, rp->sig->labels,
1454                                 rp->sig->ttl, rp->sig->exp, rp->sig->incep,
1455                                 rp->sig->tag, idnname(rp->sig->signer, buf, sizeof(buf)));
1456                 break;
1457         case Tcert:
1458                 if (rp->cert == nil)
1459                         fmtprint(&fstr, " type=<null> tag=<null> alg=<null>");
1460                 else
1461                         fmtprint(&fstr, " type=%d tag=%d alg=%d",
1462                                 rp->cert->type, rp->cert->tag, rp->cert->alg);
1463                 break;
1464         case Tcaa:
1465                 if (rp->caa == nil)
1466                         fmtprint(&fstr, " flags=<null> tag=<null> value=<null>");
1467                 else
1468                         fmtprint(&fstr, " flags=%d tag=%s value=%.*s",
1469                                 rp->caa->flags, dnname(rp->caa->tag),
1470                                 rp->caa->dlen, (char*)rp->caa->data);
1471                 break;
1472         }
1473 out:
1474         strp = fmtstrflush(&fstr);
1475         rv = fmtstrcpy(f, strp);
1476         free(strp);
1477         return rv;
1478 }
1479
1480 void
1481 warning(char *fmt, ...)
1482 {
1483         char dnserr[256];
1484         va_list arg;
1485
1486         va_start(arg, fmt);
1487         vseprint(dnserr, dnserr+sizeof(dnserr), fmt, arg);
1488         va_end(arg);
1489         syslog(1, logfile, dnserr);             /* on console too */
1490 }
1491
1492 void
1493 dnslog(char *fmt, ...)
1494 {
1495         char dnserr[256];
1496         va_list arg;
1497
1498         va_start(arg, fmt);
1499         vseprint(dnserr, dnserr+sizeof(dnserr), fmt, arg);
1500         va_end(arg);
1501         syslog(0, logfile, dnserr);
1502 }
1503
1504 /*
1505  *  create a slave process to handle a request to avoid one request blocking
1506  *  another
1507  */
1508 void
1509 slave(Request *req)
1510 {
1511         int ppid, procs;
1512
1513         if(req->isslave)
1514                 return;         /* we're already a slave process */
1515
1516         /*
1517          * These calls to putactivity cannot block.
1518          * After getactivity(), the current process is counted
1519          * twice in dnvars.active (one will pass to the child).
1520          * If putactivity tries to wait for dnvars.active == 0,
1521          * it will never happen.
1522          */
1523
1524         /* limit parallelism */
1525         procs = getactivity(req, 1);
1526         if(procs > stats.slavehiwat)
1527                 stats.slavehiwat = procs;
1528         if(procs > Maxactive){
1529                 if(traceactivity)
1530                         dnslog("[%d] too much activity", getpid());
1531                 putactivity(1);
1532                 return;
1533         }
1534
1535         /*
1536          * parent returns to main loop, child does the work.
1537          * don't change note group.
1538          */
1539         ppid = getpid();
1540         switch(rfork(RFPROC|RFMEM|RFNOWAIT)){
1541         case -1:
1542                 putactivity(1);
1543                 break;
1544         case 0:
1545                 procsetname("request slave of pid %d", ppid);
1546                 if(traceactivity)
1547                         dnslog("[%d] take activity from %d", getpid(), ppid);
1548                 req->isslave = 1;       /* why not `= getpid()'? */
1549                 break;
1550         default:
1551                 /*
1552                  * this relies on rfork producing separate, initially-identical
1553                  * stacks, thus giving us two copies of `req', one in each
1554                  * process.
1555                  */
1556                 alarm(0);
1557                 longjmp(req->mret, 1);
1558         }
1559 }
1560
1561 static int
1562 blockequiv(Block *a, Block *b)
1563 {
1564         return  a->dlen == b->dlen &&
1565                 memcmp(a->data, b->data, a->dlen) == 0;
1566 }
1567
1568 static int
1569 keyequiv(Key *a, Key *b)
1570 {
1571         return  a->flags == b->flags &&
1572                 a->proto == b->proto &&
1573                 a->alg == b->alg &&
1574                 blockequiv(a, b);
1575 }
1576
1577 static int
1578 certequiv(Cert *a, Cert *b)
1579 {
1580         return  a->type == a->type &&
1581                 a->tag == a->tag &&
1582                 a->alg == a->alg &&
1583                 blockequiv(a, b);
1584 }
1585
1586 static int
1587 txtequiv(Txt *a, Txt *b)
1588 {
1589         char *ap, *ae, *bp, *be;
1590         int n;
1591
1592         for(ap = ae = bp = be = nil;;ap += n, bp += n){
1593                 while(a != nil && (ap == nil || (ap == ae && (a = a->next) != nil)))
1594                         ap = a->p, ae = ap + strlen(ap);
1595                 while(b != nil && (bp == nil || (bp == be && (b = b->next) != nil)))
1596                         bp = b->p, be = bp + strlen(bp);
1597                 if(a == b || a == nil || b == nil)
1598                         break;
1599                 n = ae - ap;
1600                 if(be - bp < n)
1601                         n = be - bp;
1602                 if(memcmp(ap, bp, n) != 0)
1603                         return 0;
1604         }
1605         return a == b;
1606 }
1607
1608 static int
1609 rrequiv(RR *r1, RR *r2)
1610 {
1611         if(r1->owner != r2->owner
1612         || r1->type != r2->type
1613         || r1->arg0 != r2->arg0
1614         || r1->arg1 != r2->arg1)
1615                 return 0;
1616         switch(r1->type){
1617         case Tkey:
1618                 return keyequiv(r1->key, r2->key);
1619         case Tcert:
1620                 return certequiv(r1->cert, r2->cert);
1621         case Tsig:
1622                 return r1->sig->signer == r2->sig->signer && certequiv(r1->sig, r2->sig);
1623         case Tnull:
1624                 return blockequiv(r1->null, r2->null);
1625         case Ttxt:
1626                 return txtequiv(r1->txt, r2->txt);
1627         case Tcaa:
1628                 return r1->caa->flags == r2->caa->flags && r1->caa->tag == r2->caa->tag && blockequiv(r1->caa, r2->caa);
1629         }
1630         return 1;
1631 }
1632
1633 void
1634 unique(RR *rp)
1635 {
1636         RR **l, *nrp;
1637
1638         for(; rp; rp = rp->next){
1639                 l = &rp->next;
1640                 for(nrp = *l; nrp; nrp = *l)
1641                         if(rrequiv(rp, nrp)){
1642                                 *l = nrp->next;
1643                                 rrfree(nrp);
1644                         } else
1645                                 l = &nrp->next;
1646         }
1647 }
1648
1649 /*
1650  *  true if second domain is subsumed by the first
1651  */
1652 int
1653 subsume(char *higher, char *lower)
1654 {
1655         int hn, ln;
1656
1657         ln = strlen(lower);
1658         hn = strlen(higher);
1659         if (ln < hn || cistrcmp(lower + ln - hn, higher) != 0 ||
1660             ln > hn && hn != 0 && lower[ln - hn - 1] != '.')
1661                 return 0;
1662         return 1;
1663 }
1664
1665 /*
1666  *  randomize the order we return items to provide some
1667  *  load balancing for servers.
1668  *
1669  *  only randomize the first class of entries
1670  */
1671 RR*
1672 randomize(RR *rp)
1673 {
1674         RR *first, *last, *x, *base;
1675         ulong n;
1676
1677         if(rp == nil || rp->next == nil)
1678                 return rp;
1679
1680         /* just randomize addresses, mx's and ns's */
1681         for(x = rp; x; x = x->next)
1682                 if(x->type != Ta && x->type != Taaaa &&
1683                     x->type != Tmx && x->type != Tns)
1684                         return rp;
1685
1686         base = rp;
1687
1688         n = rand();
1689         last = first = nil;
1690         while(rp != nil){
1691                 /* stop randomizing if we've moved past our class */
1692                 if(base->auth != rp->auth || base->db != rp->db){
1693                         last->next = rp;
1694                         break;
1695                 }
1696
1697                 /* unchain */
1698                 x = rp;
1699                 rp = x->next;
1700                 x->next = nil;
1701
1702                 if(n&1){
1703                         /* add to tail */
1704                         if(last == nil)
1705                                 first = x;
1706                         else
1707                                 last->next = x;
1708                         last = x;
1709                 } else {
1710                         /* add to head */
1711                         if(last == nil)
1712                                 last = x;
1713                         x->next = first;
1714                         first = x;
1715                 }
1716
1717                 /* reroll the dice */
1718                 n >>= 1;
1719         }
1720
1721         return first;
1722 }
1723
1724 static int
1725 sencodefmt(Fmt *f)
1726 {
1727         int i, len, ilen, rv;
1728         char *out, *buf;
1729         uchar *b;
1730         char obuf[64];          /* rsc optimization */
1731
1732         if(!(f->flags&FmtPrec) || f->prec < 1)
1733                 goto error;
1734
1735         b = va_arg(f->args, uchar*);
1736         if(b == nil)
1737                 goto error;
1738
1739         /* if it's a printable, go for it */
1740         len = f->prec;
1741         for(i = 0; i < len; i++)
1742                 if(!isprint(b[i]))
1743                         break;
1744         if(i == len){
1745                 if(len >= sizeof obuf)
1746                         len = sizeof(obuf)-1;
1747                 memmove(obuf, b, len);
1748                 obuf[len] = 0;
1749                 fmtstrcpy(f, obuf);
1750                 return 0;
1751         }
1752
1753         ilen = f->prec;
1754         f->prec = 0;
1755         f->flags &= ~FmtPrec;
1756         len = 2*ilen + 1;
1757         if(len > sizeof(obuf)){
1758                 buf = malloc(len);
1759                 if(buf == nil)
1760                         goto error;
1761         } else
1762                 buf = obuf;
1763
1764         /* convert */
1765         out = buf;
1766         rv = enc16(out, len, b, ilen);
1767         if(rv < 0)
1768                 goto error;
1769
1770         fmtstrcpy(f, buf);
1771         if(buf != obuf)
1772                 free(buf);
1773         return 0;
1774
1775 error:
1776         return fmtstrcpy(f, "<encodefmt>");
1777 }
1778
1779 void*
1780 emalloc(int size)
1781 {
1782         char *x;
1783
1784         x = mallocz(size, 1);
1785         if(x == nil)
1786                 abort();
1787         setmalloctag(x, getcallerpc(&size));
1788         return x;
1789 }
1790
1791 char*
1792 estrdup(char *s)
1793 {
1794         int size;
1795         char *p;
1796
1797         size = strlen(s);
1798         p = mallocz(size+1, 0);
1799         if(p == nil)
1800                 abort();
1801         memmove(p, s, size);
1802         p[size] = 0;
1803         setmalloctag(p, getcallerpc(&s));
1804         return p;
1805 }
1806
1807 /*
1808  *  create a pointer record
1809  */
1810 static RR*
1811 mkptr(DN *dp, char *ptr, ulong ttl)
1812 {
1813         DN *ipdp;
1814         RR *rp;
1815
1816         ipdp = dnlookup(ptr, Cin, 1);
1817
1818         rp = rralloc(Tptr);
1819         rp->ptr = dp;
1820         rp->owner = ipdp;
1821         rp->db = 1;
1822         if(ttl)
1823                 rp->ttl = ttl;
1824         return rp;
1825 }
1826
1827 void    bytes2nibbles(uchar *nibbles, uchar *bytes, int nbytes);
1828
1829 /*
1830  *  look for all ip addresses in this network and make
1831  *  pointer records for them.
1832  */
1833 void
1834 dnptr(uchar *net, uchar *mask, char *dom, int forwtype, int subdoms, int ttl)
1835 {
1836         int i, j, len;
1837         char *p, *e;
1838         char ptr[Domlen];
1839         uchar *ipp;
1840         uchar ip[IPaddrlen], nnet[IPaddrlen];
1841         uchar nibip[IPaddrlen*2];
1842         DN *dp;
1843         RR *rp, *nrp, *first, **l;
1844
1845         l = &first;
1846         first = nil;
1847         for(i = 0; i < HTLEN; i++)
1848                 for(dp = ht[i]; dp; dp = dp->next)
1849                         for(rp = dp->rr; rp; rp = rp->next){
1850                                 if(rp->type != forwtype || rp->negative)
1851                                         continue;
1852                                 parseip(ip, rp->ip->name);
1853                                 maskip(ip, mask, nnet);
1854                                 if(ipcmp(net, nnet) != 0)
1855                                         continue;
1856
1857                                 ipp = ip;
1858                                 len = IPaddrlen;
1859                                 if (forwtype == Taaaa) {
1860                                         bytes2nibbles(nibip, ip, IPaddrlen);
1861                                         ipp = nibip;
1862                                         len = 2*IPaddrlen;
1863                                 }
1864
1865                                 p = ptr;
1866                                 e = ptr+sizeof(ptr);
1867                                 for(j = len - 1; j >= len - subdoms; j--)
1868                                         p = seprint(p, e, (forwtype == Ta?
1869                                                 "%d.": "%x."), ipp[j]);
1870                                 seprint(p, e, "%s", dom);
1871
1872                                 nrp = mkptr(dp, ptr, ttl);
1873                                 *l = nrp;
1874                                 l = &nrp->next;
1875                         }
1876
1877         for(rp = first; rp != nil; rp = nrp){
1878                 nrp = rp->next;
1879                 rp->next = nil;
1880                 dp = rp->owner;
1881                 rrattach(rp, Authoritative);
1882                 dnagenever(dp);
1883         }
1884 }
1885
1886 void
1887 addserver(Server **l, char *name)
1888 {
1889         Server *s;
1890         int n;
1891
1892         while(*l)
1893                 l = &(*l)->next;
1894         n = strlen(name);
1895         s = malloc(sizeof(Server)+n+1);
1896         if(s == nil)
1897                 return;
1898         s->name = (char*)(s+1);
1899         memmove(s->name, name, n);
1900         s->name[n] = 0;
1901         s->next = nil;
1902         *l = s;
1903 }
1904
1905 Server*
1906 copyserverlist(Server *s)
1907 {
1908         Server *ns;
1909
1910         for(ns = nil; s != nil; s = s->next)
1911                 addserver(&ns, s->name);
1912         return ns;
1913 }
1914
1915
1916 /* from here down is copied to ip/snoopy/dns.c periodically to update it */
1917
1918 /*
1919  *  convert an integer RR type to it's ascii name
1920  */
1921 char*
1922 rrname(int type, char *buf, int len)
1923 {
1924         char *t;
1925
1926         t = nil;
1927         if(type >= 0 && type < nelem(rrtname))
1928                 t = rrtname[type];
1929         if(t==nil){
1930                 snprint(buf, len, "%d", type);
1931                 t = buf;
1932         }
1933         return t;
1934 }
1935
1936 /*
1937  *  free a list of resource records and any related structs
1938  */
1939 void
1940 rrfreelist(RR *rp)
1941 {
1942         RR *next;
1943
1944         for(; rp; rp = next){
1945                 next = rp->next;
1946                 rrfree(rp);
1947         }
1948 }
1949
1950 void
1951 freeserverlist(Server *s)
1952 {
1953         Server *next;
1954
1955         for(; s != nil; s = next){
1956                 next = s->next;
1957                 memset(s, 0, sizeof *s);        /* cause trouble */
1958                 free(s);
1959         }
1960 }
1961
1962 /*
1963  *  allocate a resource record of a given type
1964  */
1965 RR*
1966 rralloc(int type)
1967 {
1968         RR *rp;
1969
1970         rp = emalloc(sizeof(*rp));
1971         rp->magic = RRmagic;
1972         rp->pc = getcallerpc(&type);
1973         rp->type = type;
1974         if (rp->type != type)
1975                 dnslog("rralloc: bogus type %d", type);
1976         setmalloctag(rp, rp->pc);
1977         switch(type){
1978         case Tsoa:
1979                 rp->soa = emalloc(sizeof(*rp->soa));
1980                 rp->soa->slaves = nil;
1981                 setmalloctag(rp->soa, rp->pc);
1982                 break;
1983         case Tsrv:
1984                 rp->srv = emalloc(sizeof(*rp->srv));
1985                 setmalloctag(rp->srv, rp->pc);
1986                 break;
1987         case Tdnskey:
1988         case Tkey:
1989                 rp->key = emalloc(sizeof(*rp->key));
1990                 setmalloctag(rp->key, rp->pc);
1991                 break;
1992         case Tcaa:
1993                 rp->caa = emalloc(sizeof(*rp->caa));
1994                 setmalloctag(rp->caa, rp->pc);
1995                 break;
1996         case Tcert:
1997                 rp->cert = emalloc(sizeof(*rp->cert));
1998                 setmalloctag(rp->cert, rp->pc);
1999                 break;
2000         case Tsig:
2001                 rp->sig = emalloc(sizeof(*rp->sig));
2002                 setmalloctag(rp->sig, rp->pc);
2003                 break;
2004         case Tnull:
2005                 rp->null = emalloc(sizeof(*rp->null));
2006                 setmalloctag(rp->null, rp->pc);
2007                 break;
2008         }
2009         rp->ttl = 0;
2010         rp->expire = 0;
2011         rp->next = 0;
2012         return rp;
2013 }
2014
2015 /*
2016  *  free a resource record and any related structs
2017  */
2018 void
2019 rrfree(RR *rp)
2020 {
2021         Txt *t;
2022
2023         assert(rp->magic == RRmagic && !rp->cached);
2024
2025         switch(rp->type){
2026         case Tsoa:
2027                 freeserverlist(rp->soa->slaves);
2028                 memset(rp->soa, 0, sizeof *rp->soa);    /* cause trouble */
2029                 free(rp->soa);
2030                 break;
2031         case Tsrv:
2032                 memset(rp->srv, 0, sizeof *rp->srv);    /* cause trouble */
2033                 free(rp->srv);
2034                 break;
2035         case Tdnskey:
2036         case Tkey:
2037                 free(rp->key->data);
2038                 memset(rp->key, 0, sizeof *rp->key);    /* cause trouble */
2039                 free(rp->key);
2040                 break;
2041         case Tcert:
2042                 free(rp->cert->data);
2043                 memset(rp->cert, 0, sizeof *rp->cert);  /* cause trouble */
2044                 free(rp->cert);
2045                 break;
2046         case Tsig:
2047                 free(rp->sig->data);
2048                 memset(rp->sig, 0, sizeof *rp->sig);    /* cause trouble */
2049                 free(rp->sig);
2050                 break;
2051         case Tnull:
2052                 free(rp->null->data);
2053                 memset(rp->null, 0, sizeof *rp->null);  /* cause trouble */
2054                 free(rp->null);
2055                 break;
2056         case Tcaa:
2057                 free(rp->caa->data);
2058                 memset(rp->caa, 0, sizeof *rp->caa);    /* cause trouble */
2059                 break;
2060         case Ttxt:
2061                 while(t = rp->txt){
2062                         rp->txt = t->next;
2063                         free(t->p);
2064                         memset(t, 0, sizeof *t);        /* cause trouble */
2065                         free(t);
2066                 }
2067                 break;
2068         }
2069
2070         memset(rp, 0, sizeof *rp);              /* cause trouble */
2071         rp->magic = ~RRmagic;
2072         free(rp);
2073 }