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