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