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