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