sys/src/cmd/ndb/dn.c

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