sys/src/cmd/ndb/dn.c

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