mdnsd.c

   1 #include <string.h>
   2 #include <ctype.h>
   3 #include <stdlib.h>
   4 #include <arpa/inet.h>
   5 #include "mdnsd.h"
   6 #include <stdio.h>
   7
   8 // size of query/publish hashes
   9 #define SPRIME 108
  10 // size of cache hash
  11 #define LPRIME 1009
  12 // brute force garbage cleanup frequency, rarely needed (daily default)
  13 #define GC 86400
  14
  15 /* messy, but it's the best/simplest balance I can find at the moment
  16 Some internal data types, and a few hashes: querys, answers, cached, and records (published, unique and shared)
  17 Each type has different semantics for processing, both for timeouts, incoming, and outgoing I/O
  18 They inter-relate too, like records affect the querys they are relevant to
  19 Nice things about MDNS: we only publish once (and then ask asked), and only query once, then just expire records we've got cached
  20 */
  21
  22 struct query
  23 {
  24     char *name;
  25     int type;
  26     unsigned long int nexttry;
  27     int tries;
  28     int (*answer)(mdnsda, void *);
  29     void *arg;
  30     struct query *next, *list;
  31 };
  32
  33 struct unicast
  34 {
  35     int id;
  36     unsigned long int to;
  37     unsigned short int port;
  38     mdnsdr r;
  39     struct unicast *next;
  40 };
  41
  42 struct cached
  43 {
  44     struct mdnsda_struct rr;
  45     struct query *q;
  46     struct cached *next;
  47 };
  48
  49 struct mdnsdr_struct
  50 {
  51     struct mdnsda_struct rr;
  52     char unique; // # of checks performed to ensure
  53     int tries;
  54     void (*conflict)(char *, int, void *);
  55     void *arg;
  56     struct mdnsdr_struct *next, *list;
  57 };
  58
  59 struct mdnsd_struct
  60 {
  61     char shutdown;
  62     unsigned long int expireall, checkqlist;
  63     struct timeval now, sleep, pause, probe, publish;
  64     int class, frame;
  65     struct cached *cache[LPRIME];
  66     struct mdnsdr_struct *published[SPRIME], *probing, *a_now, *a_pause, *a_publish;
  67     struct unicast *uanswers;
  68     struct query *queries[SPRIME], *qlist;
  69 };
  70
  71 int _namehash(const char *s)
  72 {
  73     const unsigned char *name = (const unsigned char *)s;
  74     unsigned long h = 0, g;
  75
  76     while (*name)
  77     { /* do some fancy bitwanking on the string */
  78         h = (h << 4) + (unsigned long)(tolower (*name++));
  79         if ((g = (h & 0xF0000000UL))!=0)
  80             h ^= (g >> 24);
  81         h &= ~g;
  82     }
  83
  84     return (int)h;
  85 }
  86
  87 // basic linked list and hash primitives
  88 struct query *_q_next(mdnsd d, struct query *q, char *host, int type)
  89 {
  90     if(q == 0) q = d->queries[_namehash(host) % SPRIME];
  91     else q = q->next;
  92     for(;q != 0; q = q->next)
  93         if((q->type == QTYPE_ANY || q->type == type) && strcasecmp(q->name, host) == 0)
  94             return q;
  95     return 0;
  96 }
  97 struct cached *_c_next(mdnsd d, struct cached *c, char *host, int type)
  98 {
  99     if(c == 0) c = d->cache[_namehash(host) % LPRIME];
 100     else c = c->next;
 101     for(;c != 0; c = c->next)
 102         if((type == c->rr.type || type == QTYPE_ANY) && strcasecmp(c->rr.name, host) == 0)
 103             return c;
 104     return 0;
 105 }
 106 mdnsdr _r_next(mdnsd d, mdnsdr r, char *host, int type)
 107 {
 108     if(r == 0) r = d->published[_namehash(host) % SPRIME];
 109     else r = r->next;
 110     for(;r != 0; r = r->next)
 111         if((type == r->rr.type || type == QTYPE_ANY) && strcasecmp(r->rr.name, host) == 0)
 112             return r;
 113     return 0;
 114 }
 115
 116 int _rr_len(mdnsda rr)
 117 {
 118     int len = 12; // name is always compressed (dup of earlier), plus normal stuff
 119     if(rr->rdata) len += rr->rdlen;
 120     if(rr->rdname) len += strlen(rr->rdname); // worst case
 121     if(rr->ip) len += 4;
 122     if(rr->type == QTYPE_PTR) len += 6; // srv record stuff
 123     return len;
 124 }
 125
 126 int _a_match(struct resource *r, mdnsda a)
 127 { // compares new rdata with known a, painfully
 128     if(strcasecmp(r->name,a->name) || (r->type != QTYPE_ANY && r->type != a->type)) return 0;
 129     if(!strcasecmp(r->name,a->name) && r->type == QTYPE_ANY) return 1;
 130     if(r->type == QTYPE_SRV && !strcasecmp(r->known.srv.name,a->rdname) && a->srv.port == r->known.srv.port && a->srv.weight == r->known.srv.weight && a->srv.priority == r->known.srv.priority) return 1;
 131     if((r->type == QTYPE_PTR || r->type == QTYPE_NS || r->type == QTYPE_CNAME) && !strcasecmp(a->rdname,r->known.ns.name)) return 1;
 132     if(r->rdlength == a->rdlen && !memcmp(r->rdata,a->rdata,r->rdlength)) return 1;
 133     return 0;
 134 }
 135
 136 // compare time values easily
 137 int _tvdiff(struct timeval old, struct timeval new)
 138 {
 139     int udiff = 0;
 140     if(old.tv_sec != new.tv_sec) udiff = (new.tv_sec - old.tv_sec) * 1000000;
 141     return (new.tv_usec - old.tv_usec) + udiff;
 142 }
 143
 144 // make sure not already on the list, then insert
 145 void _r_push(mdnsdr *list, mdnsdr r)
 146 {
 147     mdnsdr cur;
 148     for(cur = *list; cur != 0; cur = cur->list)
 149         if(cur == r) return;
 150     r->list = *list;
 151     *list = r;
 152 }
 153
 154 // set this r to probing, set next probe time
 155 void _r_probe(mdnsd d, mdnsdr r)
 156 {
 157 }
 158
 159 // force any r out right away, if valid
 160 void _r_publish(mdnsd d, mdnsdr r)
 161 {
 162     if(r->unique && r->unique < 5) return; // probing already
 163     r->tries = 0;
 164     d->publish.tv_sec = d->now.tv_sec; d->publish.tv_usec = d->now.tv_usec;
 165     _r_push(&d->a_publish,r);
 166 }
 167
 168 // send r out asap
 169 void _r_send(mdnsd d, mdnsdr r)
 170 {
 171     if(r->tries < 4)
 172     { // being published, make sure that happens soon
 173         d->publish.tv_sec = d->now.tv_sec; d->publish.tv_usec = d->now.tv_usec;
 174         return;
 175     }
 176     if(r->unique)
 177     { // known unique ones can be sent asap
 178         _r_push(&d->a_now,r);
 179         return;
 180     }
 181     // set d->pause.tv_usec to random 20-120 msec
 182     d->pause.tv_sec = d->now.tv_sec;
 183     d->pause.tv_usec = d->now.tv_usec + ((d->now.tv_usec % 101) + 20) * 1000;
 184     if (d->pause.tv_usec >= 1000000)
 185     {
 186         d->pause.tv_sec++;
 187         d->pause.tv_usec -= 1000000;
 188     }
 189     _r_push(&d->a_pause,r);
 190 }
 191
 192 // create generic unicast response struct
 193 void _u_push(mdnsd d, mdnsdr r, int id, unsigned long int to, unsigned short int port)
 194 {
 195     struct unicast *u;
 196     u = (struct unicast *)malloc(sizeof(struct unicast));
 197     bzero(u,sizeof(struct unicast));
 198     u->r = r;
 199     u->id = id;
 200     u->to = to;
 201     u->port = port;
 202     u->next = d->uanswers;
 203     d->uanswers = u;
 204 }
 205
 206 void _q_reset(mdnsd d, struct query *q)
 207 {
 208     struct cached *cur = 0;
 209     q->nexttry = 0;
 210     q->tries = 0;
 211     while((cur = _c_next(d,cur,q->name,q->type)))
 212         if(q->nexttry == 0 || cur->rr.ttl - 7 < q->nexttry) q->nexttry = cur->rr.ttl - 7;
 213     if(q->nexttry != 0 && q->nexttry < d->checkqlist) d->checkqlist = q->nexttry;
 214 }
 215
 216 void _q_done(mdnsd d, struct query *q)
 217 { // no more query, update all it's cached entries, remove from lists
 218     struct cached *c = 0;
 219     struct query *cur;
 220     int i = _namehash(q->name) % SPRIME;
 221     while((c = _c_next(d,c,q->name,q->type))) c->q = 0;
 222     if(d->qlist == q) d->qlist = q->list;
 223     else {
 224         for(cur=d->qlist;cur->list != q;cur = cur->list);
 225         cur->list = q->list;
 226     }
 227     if(d->queries[i] == q) d->queries[i] = q->next;
 228     else {
 229         for(cur=d->queries[i];cur->next != q;cur = cur->next);
 230         cur->next = q->next;
 231     }
 232     free(q->name);
 233     free(q);
 234 }
 235
 236 void _r_done(mdnsd d, mdnsdr r)
 237 { // buh-bye, remove from hash and free
 238     mdnsdr cur = 0;
 239     int i = _namehash(r->rr.name) % SPRIME;
 240     if(d->published[i] == r) d->published[i] = r->next;
 241     else {
 242         for(cur=d->published[i];cur && cur->next != r;cur = cur->next);
 243         if(cur) cur->next = r->next;
 244     }
 245     free(r->rr.name);
 246     free(r->rr.rdata);
 247     free(r->rr.rdname);
 248     free(r);
 249 }
 250
 251 void _q_answer(mdnsd d, struct cached *c)
 252 { // call the answer function with this cached entry
 253     if(c->rr.ttl <= d->now.tv_sec) c->rr.ttl = 0;
 254     if(c->q->answer(&c->rr,c->q->arg) == -1) _q_done(d, c->q);
 255 }
 256
 257 void _conflict(mdnsd d, mdnsdr r)
 258 {
 259     r->conflict(r->rr.name,r->rr.type,r->arg);
 260     mdnsd_done(d,r);
 261 }
 262
 263 void _c_expire(mdnsd d, struct cached **list)
 264 { // expire any old entries in this list
 265     struct cached *next, *cur = *list, *last = 0;
 266     while(cur != 0)
 267     {
 268         next = cur->next;
 269         if(d->now.tv_sec >= cur->rr.ttl)
 270         {
 271             if(last) last->next = next;
 272             if(*list == cur) *list = next; // update list pointer if the first one expired
 273             if(cur->q) _q_answer(d,cur);
 274             free(cur->rr.name);
 275             free(cur->rr.rdata);
 276             free(cur->rr.rdname);
 277             free(cur);
 278         }else{
 279             last = cur;
 280         }
 281         cur = next;
 282     }
 283 }
 284
 285 // brute force expire any old cached records
 286 void _gc(mdnsd d)
 287 {
 288     int i;
 289     for(i=0;i<LPRIME;i++)
 290         if(d->cache[i]) _c_expire(d,&d->cache[i]);
 291     d->expireall = d->now.tv_sec + GC;
 292 }
 293
 294 void _cache(mdnsd d, struct resource *r)
 295 {
 296     struct cached *c = 0;
 297     int i = _namehash(r->name) % LPRIME;
 298
 299     if(r->class == 32768 + d->class)
 300     { // cache flush
 301         while((c = _c_next(d,c,r->name,r->type))) c->rr.ttl = 0;
 302         _c_expire(d,&d->cache[i]);
 303     }
 304
 305     if(r->ttl == 0)
 306     { // process deletes
 307         while((c = _c_next(d,c,r->name,r->type)))
 308             if(_a_match(r,&c->rr))
 309             {
 310                 c->rr.ttl = 0;
 311             }
 312         _c_expire(d,&d->cache[i]);
 313         return;
 314     }
 315
 316     c = (struct cached *)malloc(sizeof(struct cached));
 317     bzero(c,sizeof(struct cached));
 318     c->rr.name = strdup(r->name);
 319     c->rr.type = r->type;
 320     c->rr.ttl = d->now.tv_sec + (r->ttl / 2) + 8; // XXX hack for now, BAD SPEC, start retrying just after half-waypoint, then expire
 321     c->rr.rdlen = r->rdlength;
 322     c->rr.rdata = (unsigned char *)malloc(r->rdlength);
 323     memcpy(c->rr.rdata,r->rdata,r->rdlength);
 324     switch(r->type)
 325     {
 326     case QTYPE_A:
 327         c->rr.ip = r->known.a.ip;
 328         break;
 329     case QTYPE_NS:
 330     case QTYPE_CNAME:
 331     case QTYPE_PTR:
 332         c->rr.rdname = strdup(r->known.ns.name);
 333         break;
 334     case QTYPE_SRV:
 335         c->rr.rdname = strdup(r->known.srv.name);
 336         c->rr.srv.port = r->known.srv.port;
 337         c->rr.srv.weight = r->known.srv.weight;
 338         c->rr.srv.priority = r->known.srv.priority;
 339         break;
 340     }
 341     c->next = d->cache[i];
 342     d->cache[i] = c;
 343     if((c->q = _q_next(d, 0, r->name, r->type)))
 344         _q_answer(d,c);
 345 }
 346
 347 void _a_copy(struct message *m, mdnsda a)
 348 { // copy the data bits only
 349     if(a->rdata) { message_rdata_raw(m, a->rdata, a->rdlen); return; }
 350     if(a->ip) message_rdata_long(m, a->ip);
 351     if(a->type == QTYPE_SRV) message_rdata_srv(m, a->srv.priority, a->srv.weight, a->srv.port, a->rdname);
 352     else if(a->rdname) message_rdata_name(m, a->rdname);
 353 }
 354
 355 int _r_out(mdnsd d, struct message *m, mdnsdr *list)
 356 { // copy a published record into an outgoing message
 357     mdnsdr r;
 358     int ret = 0;
 359     while((r = *list) != 0 && message_packet_len(m) + _rr_len(&r->rr) < d->frame)
 360     {
 361         *list = r->list;
 362         ret++;
 363         if(r->unique)
 364             message_an(m, r->rr.name, r->rr.type, d->class + 32768, r->rr.ttl);
 365         else
 366             message_an(m, r->rr.name, r->rr.type, d->class, r->rr.ttl);
 367         _a_copy(m, &r->rr);
 368         if(r->rr.ttl == 0) _r_done(d,r);
 369     }
 370     return ret;
 371 }
 372
 373
 374 mdnsd mdnsd_new(int class, int frame)
 375 {
 376     mdnsd d;
 377     d = (mdnsd)malloc(sizeof(struct mdnsd_struct));
 378     bzero(d,sizeof(struct mdnsd_struct));
 379     gettimeofday(&d->now,0);
 380     d->expireall = d->now.tv_sec + GC;
 381     d->class = class;
 382     d->frame = frame;
 383     return d;
 384 }
 385
 386 void mdnsd_shutdown(mdnsd d)
 387 { // shutting down, zero out ttl and push out all records
 388     int i;
 389     mdnsdr cur,next;
 390     d->a_now = 0;
 391     for(i=0;i<SPRIME;i++)
 392         for(cur = d->published[i]; cur != 0;)
 393         {
 394             next = cur->next;
 395             cur->rr.ttl = 0;
 396             cur->list = d->a_now;
 397             d->a_now = cur;
 398             cur = next;
 399         }
 400     d->shutdown = 1;
 401 }
 402
 403 void mdnsd_flush(mdnsd d)
 404 {
 405     // set all querys to 0 tries
 406     // free whole cache
 407     // set all mdnsdr to probing
 408     // reset all answer lists
 409 }
 410
 411 void mdnsd_free(mdnsd d)
 412 {
 413     // loop through all hashes, free everything
 414     // free answers if any
 415     free(d);
 416 }
 417
 418 char *decode_type (unsigned short type)
 419 {
 420   switch (type) {
 421     case QTYPE_A:     return "A";
 422     case QTYPE_NS:    return "NS";
 423     case QTYPE_CNAME: return "CNAME";
 424     case QTYPE_PTR:   return "PTR";
 425     case QTYPE_TXT:   return "TXT";
 426     case QTYPE_SRV:   return "SRV";
 427     default:   return "???";
 428   }
 429 }
 430
 431 void mdnsd_res_dump (FILE *file, struct resource *res)
 432 {
 433   fprintf (file, "%s \"%s\" = ",
 434            decode_type (res->type), res->name);
 435   switch (res->type)
 436     {
 437       case QTYPE_A:
 438         fprintf (file, "%ld.%ld.%ld.%ld\n",
 439                  (res->known.a.ip >> 24) & 0xff,
 440                  (res->known.a.ip >> 16) & 0xff,
 441                  (res->known.a.ip >> 8) & 0xff,
 442                  (res->known.a.ip >> 0) & 0xff);
 443         break;
 444       case QTYPE_NS:
 445         fprintf (file, "%s\n", res->known.ns.name);
 446         break;
 447       case QTYPE_CNAME:
 448         fprintf (file, "%s\n", res->known.cname.name);
 449         break;
 450       case QTYPE_PTR:
 451         fprintf (file, "%s\n", res->known.ptr.name);
 452         break;
 453       case QTYPE_SRV:
 454         fprintf (file, "%s:%d\n", res->known.srv.name, res->known.srv.port);
 455         break;
 456       default:
 457         fprintf (file, "???\n");
 458     }
 459 }
 460
 461 void mdnsd_dump (FILE *file, struct message *m, char *type)
 462 {
 463   int i;
 464   fprintf (file, "==== %s message ====\n", type);
 465   if (m->header.qr == 0 && m->qdcount > 0)
 466     {
 467       fprintf (file, "Questions:\n");
 468       for (i = 0; i < m->qdcount; i++)
 469         fprintf (file, " %3d: %s \"%s\"?\n", i,
 470                  decode_type (m->qd[i].type), m->qd[i].name);
 471     }
 472   if (m->ancount > 0)
 473     {
 474       fprintf (file, "Answers:\n");
 475       for (i = 0; i < m->ancount; i++)
 476         {
 477           fprintf (file, " %3d: ", i);
 478           mdnsd_res_dump (file, &m->an[i]);
 479         }
 480     }
 481   if (m->nscount > 0)
 482     {
 483       fprintf (file, "Authority:\n");
 484       for (i = 0; i < m->nscount; i++)
 485         {
 486           fprintf (file, " %3d: ", i);
 487           mdnsd_res_dump (file, &m->ns[i]);
 488         }
 489     }
 490   if (m->arcount > 0)
 491     {
 492       fprintf (file, "Additional:\n");
 493       for (i = 0; i < m->arcount; i++)
 494         {
 495           fprintf (file, " %3d: ", i);
 496           mdnsd_res_dump (file, &m->ar[i]);
 497         }
 498     }
 499   fprintf (file, "\n");
 500 }
 501
 502 void mdnsd_in(mdnsd d, struct message *m, unsigned long int ip, unsigned short int port)
 503 {
 504     int i, j;
 505     mdnsdr r;
 506     int have_match;
 507     int may_conflict;
 508
 509     if(d->shutdown) return;
 510
 511     mdnsd_dump (stderr, m, "incoming");
 512
 513     gettimeofday(&d->now,0);
 514
 515     if(m->header.qr == 0)
 516     {
 517         for(i=0;i<m->qdcount;i++)
 518         { // process each query
 519             if(m->qd[i].class != d->class || (r = _r_next(d,0,m->qd[i].name,m->qd[i].type)) == 0) continue;
 520
 521             // send the matching unicast reply
 522             if(port != 5353) _u_push(d,r,m->id,ip,port);
 523
 524             for(;r != 0; r = _r_next(d,r,m->qd[i].name,m->qd[i].type))
 525             { // check all of our potential answers
 526                 int have_match = 0;
 527                 int may_conflict = 0;
 528
 529                 if(r->unique && r->unique < 5)
 530                 { // probing state, check for conflicts
 531                     for(j=0;j<m->nscount;j++)
 532                     { // check all to-be answers against our own
 533                         if(m->qd[i].type != m->an[j].type || strcasecmp(m->qd[i].name,m->an[j].name)) continue;
 534                         if(!_a_match(&m->an[j],&r->rr))
 535                             may_conflict = 1;
 536                         else
 537                             have_match = 1;
 538                     }
 539                     if (may_conflict && !have_match)
 540                        _conflict(d,r); // this answer isn't ours, conflict!
 541                     continue;
 542                 }
 543                 for(j=0;j<m->ancount;j++)
 544                 { // check the known answers for this question
 545                     if((m->qd[i].type != QTYPE_ANY && m->qd[i].type != m->an[j].type) || strcasecmp(m->qd[i].name,m->an[j].name)) continue;
 546                     if(_a_match(&m->an[j],&r->rr)) break; // they already have this answer
 547                 }
 548                 if(j == m->ancount) _r_send(d,r);
 549             }
 550         }
 551         return;
 552     }
 553
 554     for(i=0;i<m->ancount;i++)
 555     { // process each answer, check for a conflict, and cache
 556         have_match = 0;
 557         may_conflict = 0;
 558
 559         r = 0;
 560         while ((r = _r_next(d,r,m->an[i].name,m->an[i].type)) != 0)
 561           {
 562             if (r->unique)
 563               {
 564                 if (_a_match(&m->an[i],&r->rr) == 0)
 565                     may_conflict = 1;
 566                 else
 567                     have_match = 1;
 568               }
 569           }
 570         if (may_conflict && !have_match)
 571           {
 572             while ((r = _r_next(d,r,m->an[i].name,m->an[i].type)) != 0)
 573               {
 574                 if (r->unique && _a_match(&m->an[i],&r->rr) == 0)
 575                   _conflict(d, r);
 576               }
 577           }
 578         _cache(d,&m->an[i]);
 579     }
 580 }
 581
 582 int mdnsd_out(mdnsd d, struct message *m, unsigned long int *ip, unsigned short int *port)
 583 {
 584     mdnsdr r;
 585     int ret = 0;
 586
 587     gettimeofday(&d->now,0);
 588     bzero(m,sizeof(struct message));
 589
 590     // defaults, multicast
 591     *port = htons(5353);
 592     *ip = inet_addr("224.0.0.251");
 593     m->header.qr = 1;
 594     m->header.aa = 1;
 595
 596     if(d->uanswers)
 597     { // send out individual unicast answers
 598         struct unicast *u = d->uanswers;
 599         d->uanswers = u->next;
 600         *port = u->port;
 601         *ip = u->to;
 602         m->id = u->id;
 603         message_qd(m, u->r->rr.name, u->r->rr.type, d->class);
 604         message_an(m, u->r->rr.name, u->r->rr.type, d->class, u->r->rr.ttl);
 605         _a_copy(m, &u->r->rr);
 606         free(u);
 607         return 1;
 608     }
 609
 610 //printf("OUT: probing %X now %X pause %X publish %X\n",d->probing,d->a_now,d->a_pause,d->a_publish);
 611
 612     // accumulate any immediate responses
 613     if(d->a_now) ret += _r_out(d, m, &d->a_now);
 614
 615     if(d->a_publish && _tvdiff(d->now,d->publish) <= 0)
 616     { // check to see if it's time to send the publish retries (and unlink if done)
 617         mdnsdr next, cur = d->a_publish, last = 0;
 618         while(cur && message_packet_len(m) + _rr_len(&cur->rr) < d->frame)
 619         {
 620             next = cur->list;
 621             ret++; cur->tries++;
 622             if(cur->unique)
 623                 message_an(m, cur->rr.name, cur->rr.type, d->class + 32768, cur->rr.ttl);
 624             else
 625                 message_an(m, cur->rr.name, cur->rr.type, d->class, cur->rr.ttl);
 626             _a_copy(m, &cur->rr);
 627             if(cur->rr.ttl != 0 && cur->tries < 4)
 628             {
 629                 last = cur;
 630                 cur = next;
 631                 continue;
 632             }
 633             if(d->a_publish == cur) d->a_publish = next;
 634             if(last) last->list = next;
 635             if(cur->rr.ttl == 0) _r_done(d,cur);
 636             cur = next;
 637         }
 638         if(d->a_publish)
 639         {
 640             d->publish.tv_sec = d->now.tv_sec + 2;
 641             d->publish.tv_usec = d->now.tv_usec;
 642         }
 643     }
 644
 645     // if we're in shutdown, we're done
 646     if(d->shutdown) return ret;
 647
 648     // check if a_pause is ready
 649     if(d->a_pause && _tvdiff(d->now, d->pause) <= 0) ret += _r_out(d, m, &d->a_pause);
 650
 651     // now process questions
 652     if(ret) return ret;
 653     m->header.qr = 0;
 654     m->header.aa = 0;
 655
 656     if(d->probing && _tvdiff(d->now,d->probe) <= 0)
 657     {
 658         mdnsdr last = 0;
 659         for(r = d->probing; r != 0;)
 660         { // scan probe list to ask questions and process published
 661             if(r->unique == 4)
 662             { // done probing, publish
 663                 mdnsdr next = r->list;
 664                 if(d->probing == r)
 665                     d->probing = r->list;
 666                 else
 667                     last->list = r->list;
 668                 r->list = 0;
 669                 r->unique = 5;
 670                 _r_publish(d,r);
 671                 r = next;
 672                 continue;
 673             }
 674             message_qd(m, r->rr.name, QTYPE_ANY, d->class);
 675             last = r;
 676             r = r->list;
 677         }
 678         for(r = d->probing; r != 0; last = r, r = r->list)
 679         { // scan probe list again to append our to-be answers
 680             r->unique++;
 681             message_ns(m, r->rr.name, r->rr.type, d->class, r->rr.ttl);
 682             _a_copy(m, &r->rr);
 683             ret++;
 684         }
 685         if(ret)
 686         { // process probes again in the future
 687             d->probe.tv_sec = d->now.tv_sec;
 688             d->probe.tv_usec = d->now.tv_usec + 250000;
 689             return ret;
 690         }
 691     }
 692
 693     if(d->checkqlist && d->now.tv_sec >= d->checkqlist)
 694     { // process qlist for retries or expirations
 695         struct query *q;
 696         struct cached *c;
 697         unsigned long int nextbest = 0;
 698
 699         // ask questions first, track nextbest time
 700         for(q = d->qlist; q != 0; q = q->list)
 701             if(q->nexttry > 0 && q->nexttry <= d->now.tv_sec && q->tries < 3)
 702                 message_qd(m,q->name,q->type,d->class);
 703             else if(q->nexttry > 0 && (nextbest == 0 || q->nexttry < nextbest))
 704                 nextbest = q->nexttry;
 705
 706         // include known answers, update questions
 707         for(q = d->qlist; q != 0; q = q->list)
 708         {
 709             if(q->nexttry == 0 || q->nexttry > d->now.tv_sec) continue;
 710             if(q->tries == 3)
 711             { // done retrying, expire and reset
 712                 _c_expire(d,&d->cache[_namehash(q->name) % LPRIME]);
 713                 _q_reset(d,q);
 714                 continue;
 715             }
 716             ret++;
 717             q->nexttry = d->now.tv_sec + ++q->tries;
 718             if(nextbest == 0 || q->nexttry < nextbest)
 719                 nextbest = q->nexttry;
 720             // if room, add all known good entries
 721             c = 0;
 722             while((c = _c_next(d,c,q->name,q->type)) != 0 && c->rr.ttl > d->now.tv_sec + 8 && message_packet_len(m) + _rr_len(&c->rr) < d->frame)
 723             {
 724                 message_an(m,q->name,q->type,d->class,c->rr.ttl - d->now.tv_sec);
 725                 _a_copy(m,&c->rr);
 726             }
 727         }
 728         d->checkqlist = nextbest;
 729     }
 730
 731     if(d->now.tv_sec > d->expireall)
 732         _gc(d);
 733
 734     return ret;
 735 }
 736
 737 struct timeval *mdnsd_sleep(mdnsd d)
 738 {
 739     int sec, usec;
 740     d->sleep.tv_sec = d->sleep.tv_usec = 0;
 741     #define RET while(d->sleep.tv_usec > 1000000) {d->sleep.tv_sec++;d->sleep.tv_usec -= 1000000;} return &d->sleep;
 742
 743     // first check for any immediate items to handle
 744     if(d->uanswers || d->a_now) return &d->sleep;
 745
 746     gettimeofday(&d->now,0);
 747
 748     if(d->a_pause)
 749     { // then check for paused answers
 750         if((usec = _tvdiff(d->now,d->pause)) > 0) d->sleep.tv_usec = usec;
 751         RET;
 752     }
 753
 754     if(d->probing)
 755     { // now check for probe retries
 756         if((usec = _tvdiff(d->now,d->probe)) > 0) d->sleep.tv_usec = usec;
 757         RET;
 758     }
 759
 760     if(d->a_publish)
 761     { // now check for publish retries
 762         if((usec = _tvdiff(d->now,d->publish)) > 0) d->sleep.tv_usec = usec;
 763         RET;
 764     }
 765
 766     if(d->checkqlist)
 767     { // also check for queries with known answer expiration/retry
 768         if((sec = d->checkqlist - d->now.tv_sec) > 0) d->sleep.tv_sec = sec;
 769         RET;
 770     }
 771
 772     // last resort, next gc expiration
 773     if((sec = d->expireall - d->now.tv_sec) > 0) d->sleep.tv_sec = sec;
 774     RET;
 775 }
 776
 777 void mdnsd_query(mdnsd d, char *host, int type, int (*answer)(mdnsda a, void *arg), void *arg)
 778 {
 779     struct query *q;
 780     struct cached *cur = 0;
 781     int i = _namehash(host) % SPRIME;
 782     if(!(q = _q_next(d,0,host,type)))
 783     {
 784         if(!answer) return;
 785         q = (struct query *)malloc(sizeof(struct query));
 786         bzero(q,sizeof(struct query));
 787         q->name = strdup(host);
 788         q->type = type;
 789         q->next = d->queries[i];
 790         q->list = d->qlist;
 791         d->qlist = d->queries[i] = q;
 792         while((cur = _c_next(d,cur,q->name,q->type)))
 793             cur->q = q; // any cached entries should be associated
 794         _q_reset(d,q);
 795         q->nexttry = d->checkqlist = d->now.tv_sec; // new questin, immediately send out
 796     }
 797     if(!answer)
 798     { // no answer means we don't care anymore
 799         _q_done(d,q);
 800         return;
 801     }
 802     q->answer = answer;
 803     q->arg = arg;
 804 }
 805
 806 mdnsda mdnsd_list(mdnsd d, char *host, int type, mdnsda last)
 807 {
 808     return (mdnsda)_c_next(d,(struct cached *)last,host,type);
 809 }
 810
 811 mdnsdr mdnsd_shared(mdnsd d, char *host, int type, long int ttl)
 812 {
 813     int i = _namehash(host) % SPRIME;
 814     mdnsdr r;
 815     r = (mdnsdr)malloc(sizeof(struct mdnsdr_struct));
 816     bzero(r,sizeof(struct mdnsdr_struct));
 817     r->rr.name = strdup(host);
 818     r->rr.type = type;
 819     r->rr.ttl = ttl;
 820     r->next = d->published[i];
 821     d->published[i] = r;
 822     return r;
 823 }
 824
 825 mdnsdr mdnsd_unique(mdnsd d, char *host, int type, long int ttl, void (*conflict)(char *host, int type, void *arg), void *arg)
 826 {
 827     mdnsdr r;
 828     r = mdnsd_shared(d,host,type,ttl);
 829     r->conflict = conflict;
 830     r->arg = arg;
 831     r->unique = 1;
 832     _r_push(&d->probing,r);
 833     d->probe.tv_sec = d->now.tv_sec;
 834     d->probe.tv_usec = d->now.tv_usec;
 835     return r;
 836 }
 837
 838 void mdnsd_done(mdnsd d, mdnsdr r)
 839 {
 840     mdnsdr cur;
 841     if(r->unique && r->unique < 5)
 842     { // probing yet, zap from that list first!
 843         if(d->probing == r) d->probing = r->list;
 844         else {
 845             for(cur=d->probing;cur->list != r;cur = cur->list);
 846             cur->list = r->list;
 847         }
 848         _r_done(d,r);
 849         return;
 850     }
 851     r->rr.ttl = 0;
 852     _r_send(d,r);
 853 }
 854
 855 void mdnsd_set_raw(mdnsd d, mdnsdr r, char *data, int len)
 856 {
 857     free(r->rr.rdata);
 858     r->rr.rdata = (unsigned char *)malloc(len);
 859     memcpy(r->rr.rdata,data,len);
 860     r->rr.rdlen = len;
 861     _r_publish(d,r);
 862 }
 863
 864 void mdnsd_set_host(mdnsd d, mdnsdr r, char *name)
 865 {
 866     free(r->rr.rdname);
 867     r->rr.rdname = strdup(name);
 868     _r_publish(d,r);
 869 }
 870
 871 void mdnsd_set_ip(mdnsd d, mdnsdr r, unsigned long int ip)
 872 {
 873     r->rr.ip = ip;
 874     _r_publish(d,r);
 875 }
 876
 877 void mdnsd_set_srv(mdnsd d, mdnsdr r, int priority, int weight, int port, char *name)
 878 {
 879     r->rr.srv.priority = priority;
 880     r->rr.srv.weight = weight;
 881     r->rr.srv.port = port;
 882     mdnsd_set_host(d,r,name);
 883 }
 884