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)(mdnsdr r, 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, 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     gettimeofday(&d->now,0);
 512
 513     if(m->header.qr == 0)
 514     {
 515         for(i=0;i<m->qdcount;i++)
 516         { // process each query
 517             if(m->qd[i].class != d->class || (r = _r_next(d,0,m->qd[i].name,m->qd[i].type)) == 0) continue;
 518
 519             // send the matching unicast reply
 520             if(port != 5353) _u_push(d,r,m->id,ip,port);
 521
 522             for(;r != 0; r = _r_next(d,r,m->qd[i].name,m->qd[i].type))
 523             { // check all of our potential answers
 524                 int have_match = 0;
 525                 int may_conflict = 0;
 526
 527                 if(r->unique && r->unique < 5)
 528                 { // probing state, check for conflicts
 529                     for(j=0;j<m->nscount;j++)
 530                     { // check all to-be answers against our own
 531                         if(m->an[j].ttl == 0 || m->qd[i].type != m->an[j].type || strcasecmp(m->qd[i].name,m->an[j].name)) continue;
 532                         if(!_a_match(&m->an[j],&r->rr))
 533                             may_conflict = 1;
 534                         else
 535                             have_match = 1;
 536                     }
 537                     if (may_conflict && !have_match)
 538                        _conflict(d,r); // this answer isn't ours, conflict!
 539                     continue;
 540                 }
 541                 for(j=0;j<m->ancount;j++)
 542                 { // check the known answers for this question
 543                     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;
 544                     if(_a_match(&m->an[j],&r->rr)) break; // they already have this answer
 545                 }
 546                 if(j == m->ancount) _r_send(d,r);
 547             }
 548         }
 549         return;
 550     }
 551
 552     for(i=0;i<m->ancount;i++)
 553     { // process each answer, check for a conflict, and cache
 554         have_match = 0;
 555         may_conflict = 0;
 556
 557         r = 0;
 558         while ((r = _r_next(d,r,m->an[i].name,m->an[i].type)) != 0)
 559           {
 560             if (r->unique)
 561               {
 562                 if (_a_match(&m->an[i],&r->rr) == 0)
 563                     may_conflict = 1;
 564                 else
 565                     have_match = 1;
 566               }
 567           }
 568         if (may_conflict && !have_match)
 569           {
 570             while ((r = _r_next(d,r,m->an[i].name,m->an[i].type)) != 0)
 571               {
 572                 if (r->unique && _a_match(&m->an[i],&r->rr) == 0 && m->an[i].ttl > 0)
 573                   _conflict(d, r);
 574               }
 575           }
 576         _cache(d,&m->an[i]);
 577     }
 578 }
 579
 580 int mdnsd_out(mdnsd d, struct message *m, unsigned long int *ip, unsigned short int *port)
 581 {
 582     mdnsdr r;
 583     int ret = 0;
 584
 585     gettimeofday(&d->now,0);
 586     bzero(m,sizeof(struct message));
 587
 588     // defaults, multicast
 589     *port = htons(5353);
 590     *ip = inet_addr("224.0.0.251");
 591     m->header.qr = 1;
 592     m->header.aa = 1;
 593
 594     if(d->uanswers)
 595     { // send out individual unicast answers
 596         struct unicast *u = d->uanswers;
 597         d->uanswers = u->next;
 598         *port = u->port;
 599         *ip = u->to;
 600         m->id = u->id;
 601         message_qd(m, u->r->rr.name, u->r->rr.type, d->class);
 602         message_an(m, u->r->rr.name, u->r->rr.type, d->class, u->r->rr.ttl);
 603         _a_copy(m, &u->r->rr);
 604         free(u);
 605         return 1;
 606     }
 607
 608 //printf("OUT: probing %X now %X pause %X publish %X\n",d->probing,d->a_now,d->a_pause,d->a_publish);
 609
 610     // accumulate any immediate responses
 611     if(d->a_now) ret += _r_out(d, m, &d->a_now);
 612
 613     if(d->a_publish && _tvdiff(d->now,d->publish) <= 0)
 614     { // check to see if it's time to send the publish retries (and unlink if done)
 615         mdnsdr next, cur = d->a_publish, last = 0;
 616         while(cur && message_packet_len(m) + _rr_len(&cur->rr) < d->frame)
 617         {
 618             next = cur->list;
 619             ret++; cur->tries++;
 620             if(cur->unique)
 621                 message_an(m, cur->rr.name, cur->rr.type, d->class + 32768, cur->rr.ttl);
 622             else
 623                 message_an(m, cur->rr.name, cur->rr.type, d->class, cur->rr.ttl);
 624             _a_copy(m, &cur->rr);
 625             if(cur->rr.ttl != 0 && cur->tries < 4)
 626             {
 627                 last = cur;
 628                 cur = next;
 629                 continue;
 630             }
 631             if(d->a_publish == cur) d->a_publish = next;
 632             if(last) last->list = next;
 633             if(cur->rr.ttl == 0) _r_done(d,cur);
 634             cur = next;
 635         }
 636         if(d->a_publish)
 637         {
 638             d->publish.tv_sec = d->now.tv_sec + 2;
 639             d->publish.tv_usec = d->now.tv_usec;
 640         }
 641     }
 642
 643     // if we're in shutdown, we're done
 644     if(d->shutdown) return ret;
 645
 646     // check if a_pause is ready
 647     if(d->a_pause && _tvdiff(d->now, d->pause) <= 0) ret += _r_out(d, m, &d->a_pause);
 648
 649     // now process questions
 650     if(ret) return ret;
 651     m->header.qr = 0;
 652     m->header.aa = 0;
 653
 654     if(d->probing && _tvdiff(d->now,d->probe) <= 0)
 655     {
 656         mdnsdr last = 0;
 657         for(r = d->probing; r != 0;)
 658         { // scan probe list to ask questions and process published
 659             if(r->unique == 4)
 660             { // done probing, publish
 661                 mdnsdr next = r->list;
 662                 if(d->probing == r)
 663                     d->probing = r->list;
 664                 else
 665                     last->list = r->list;
 666                 r->list = 0;
 667                 r->unique = 5;
 668                 _r_publish(d,r);
 669                 r = next;
 670                 continue;
 671             }
 672             message_qd(m, r->rr.name, QTYPE_ANY, d->class);
 673             last = r;
 674             r = r->list;
 675         }
 676         for(r = d->probing; r != 0; last = r, r = r->list)
 677         { // scan probe list again to append our to-be answers
 678             r->unique++;
 679             message_ns(m, r->rr.name, r->rr.type, d->class, r->rr.ttl);
 680             _a_copy(m, &r->rr);
 681             ret++;
 682         }
 683         if(ret)
 684         { // process probes again in the future
 685             d->probe.tv_sec = d->now.tv_sec;
 686             d->probe.tv_usec = d->now.tv_usec + 250000;
 687             return ret;
 688         }
 689     }
 690
 691     if(d->checkqlist && d->now.tv_sec >= d->checkqlist)
 692     { // process qlist for retries or expirations
 693         struct query *q;
 694         struct cached *c;
 695         unsigned long int nextbest = 0;
 696
 697         // ask questions first, track nextbest time
 698         for(q = d->qlist; q != 0; q = q->list)
 699             if(q->nexttry > 0 && q->nexttry <= d->now.tv_sec && q->tries < 3)
 700                 message_qd(m,q->name,q->type,d->class);
 701             else if(q->nexttry > 0 && (nextbest == 0 || q->nexttry < nextbest))
 702                 nextbest = q->nexttry;
 703
 704         // include known answers, update questions
 705         for(q = d->qlist; q != 0; q = q->list)
 706         {
 707             if(q->nexttry == 0 || q->nexttry > d->now.tv_sec) continue;
 708             if(q->tries == 3)
 709             { // done retrying, expire and reset
 710                 _c_expire(d,&d->cache[_namehash(q->name) % LPRIME]);
 711                 _q_reset(d,q);
 712                 continue;
 713             }
 714             ret++;
 715             q->nexttry = d->now.tv_sec + ++q->tries;
 716             if(nextbest == 0 || q->nexttry < nextbest)
 717                 nextbest = q->nexttry;
 718             // if room, add all known good entries
 719             c = 0;
 720             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)
 721             {
 722                 message_an(m,q->name,q->type,d->class,c->rr.ttl - d->now.tv_sec);
 723                 _a_copy(m,&c->rr);
 724             }
 725         }
 726         d->checkqlist = nextbest;
 727     }
 728
 729     if(d->now.tv_sec > d->expireall)
 730         _gc(d);
 731
 732     return ret;
 733 }
 734
 735 struct timeval *mdnsd_sleep(mdnsd d)
 736 {
 737     int sec, usec;
 738     d->sleep.tv_sec = d->sleep.tv_usec = 0;
 739     #define RET while(d->sleep.tv_usec > 1000000) {d->sleep.tv_sec++;d->sleep.tv_usec -= 1000000;} return &d->sleep;
 740
 741     // first check for any immediate items to handle
 742     if(d->uanswers || d->a_now) return &d->sleep;
 743
 744     gettimeofday(&d->now,0);
 745
 746     if(d->a_pause)
 747     { // then check for paused answers
 748         if((usec = _tvdiff(d->now,d->pause)) > 0) d->sleep.tv_usec = usec;
 749         RET;
 750     }
 751
 752     if(d->probing)
 753     { // now check for probe retries
 754         if((usec = _tvdiff(d->now,d->probe)) > 0) d->sleep.tv_usec = usec;
 755         RET;
 756     }
 757
 758     if(d->a_publish)
 759     { // now check for publish retries
 760         if((usec = _tvdiff(d->now,d->publish)) > 0) d->sleep.tv_usec = usec;
 761         RET;
 762     }
 763
 764     if(d->checkqlist)
 765     { // also check for queries with known answer expiration/retry
 766         if((sec = d->checkqlist - d->now.tv_sec) > 0) d->sleep.tv_sec = sec;
 767         RET;
 768     }
 769
 770     // last resort, next gc expiration
 771     if((sec = d->expireall - d->now.tv_sec) > 0) d->sleep.tv_sec = sec;
 772     RET;
 773 }
 774
 775 void mdnsd_query(mdnsd d, char *host, int type, int (*answer)(mdnsda a, void *arg), void *arg)
 776 {
 777     struct query *q;
 778     struct cached *cur = 0;
 779     int i = _namehash(host) % SPRIME;
 780     if(!(q = _q_next(d,0,host,type)))
 781     {
 782         if(!answer) return;
 783         q = (struct query *)malloc(sizeof(struct query));
 784         bzero(q,sizeof(struct query));
 785         q->name = strdup(host);
 786         q->type = type;
 787         q->next = d->queries[i];
 788         q->list = d->qlist;
 789         d->qlist = d->queries[i] = q;
 790         while((cur = _c_next(d,cur,q->name,q->type)))
 791             cur->q = q; // any cached entries should be associated
 792         _q_reset(d,q);
 793         q->nexttry = d->checkqlist = d->now.tv_sec; // new questin, immediately send out
 794     }
 795     if(!answer)
 796     { // no answer means we don't care anymore
 797         _q_done(d,q);
 798         return;
 799     }
 800     q->answer = answer;
 801     q->arg = arg;
 802 }
 803
 804 mdnsda mdnsd_list(mdnsd d, char *host, int type, mdnsda last)
 805 {
 806     return (mdnsda)_c_next(d,(struct cached *)last,host,type);
 807 }
 808
 809 mdnsdr mdnsd_shared(mdnsd d, char *host, int type, long int ttl)
 810 {
 811     int i = _namehash(host) % SPRIME;
 812     mdnsdr r;
 813     r = (mdnsdr)malloc(sizeof(struct mdnsdr_struct));
 814     bzero(r,sizeof(struct mdnsdr_struct));
 815     r->rr.name = strdup(host);
 816     r->rr.type = type;
 817     r->rr.ttl = ttl;
 818     r->next = d->published[i];
 819     d->published[i] = r;
 820     return r;
 821 }
 822
 823 mdnsdr mdnsd_unique(mdnsd d, char *host, int type, long int ttl, void (*conflict)(mdnsdr r, char *host, int type, void *arg), void *arg)
 824 {
 825     mdnsdr r;
 826     r = mdnsd_shared(d,host,type,ttl);
 827     r->conflict = conflict;
 828     r->arg = arg;
 829     r->unique = 1;
 830     _r_push(&d->probing,r);
 831     d->probe.tv_sec = d->now.tv_sec;
 832     d->probe.tv_usec = d->now.tv_usec;
 833     return r;
 834 }
 835
 836 void mdnsd_done(mdnsd d, mdnsdr r)
 837 {
 838     mdnsdr cur;
 839     if(r->unique && r->unique < 5)
 840     { // probing yet, zap from that list first!
 841         if(d->probing == r) d->probing = r->list;
 842         else {
 843             for(cur=d->probing;cur->list != r;cur = cur->list);
 844             cur->list = r->list;
 845         }
 846         _r_done(d,r);
 847         return;
 848     }
 849     r->rr.ttl = 0;
 850     _r_send(d,r);
 851 }
 852
 853 void mdnsd_set_raw(mdnsd d, mdnsdr r, char *data, int len)
 854 {
 855     free(r->rr.rdata);
 856     r->rr.rdata = (unsigned char *)malloc(len);
 857     memcpy(r->rr.rdata,data,len);
 858     r->rr.rdlen = len;
 859     _r_publish(d,r);
 860 }
 861
 862 void mdnsd_set_host(mdnsd d, mdnsdr r, char *name)
 863 {
 864     free(r->rr.rdname);
 865     r->rr.rdname = strdup(name);
 866     _r_publish(d,r);
 867 }
 868
 869 void mdnsd_set_ip(mdnsd d, mdnsdr r, unsigned long int ip)
 870 {
 871     r->rr.ip = ip;
 872     _r_publish(d,r);
 873 }
 874
 875 void mdnsd_set_srv(mdnsd d, mdnsdr r, int priority, int weight, int port, char *name)
 876 {
 877     r->rr.srv.priority = priority;
 878     r->rr.srv.weight = weight;
 879     r->rr.srv.port = port;
 880     mdnsd_set_host(d,r,name);
 881 }
 882