8 // size of query/publish hashes
12 // brute force garbage cleanup frequency, rarely needed (daily default)
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
26 unsigned long int nexttry;
28 int (*answer)(mdnsda, void *);
30 struct query *next, *list;
37 unsigned short int port;
44 struct mdnsda_struct rr;
51 struct mdnsda_struct rr;
52 char unique; // # of checks performed to ensure
54 void (*conflict)(char *, int, void *);
56 struct mdnsdr_struct *next, *list;
62 unsigned long int expireall, checkqlist;
63 struct timeval now, sleep, pause, probe, publish;
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;
71 int _namehash(const char *s)
73 const unsigned char *name = (const unsigned char *)s;
74 unsigned long h = 0, g;
77 { /* do some fancy bitwanking on the string */
78 h = (h << 4) + (unsigned long)(tolower (*name++));
79 if ((g = (h & 0xF0000000UL))!=0)
87 // basic linked list and hash primitives
88 struct query *_q_next(mdnsd d, struct query *q, char *host, int type)
90 if(q == 0) q = d->queries[_namehash(host) % SPRIME];
92 for(;q != 0; q = q->next)
93 if((q->type == QTYPE_ANY || q->type == type) && strcasecmp(q->name, host) == 0)
97 struct cached *_c_next(mdnsd d, struct cached *c, char *host, int type)
99 if(c == 0) c = d->cache[_namehash(host) % LPRIME];
101 for(;c != 0; c = c->next)
102 if((type == c->rr.type || type == QTYPE_ANY) && strcasecmp(c->rr.name, host) == 0)
106 mdnsdr _r_next(mdnsd d, mdnsdr r, char *host, int type)
108 if(r == 0) r = d->published[_namehash(host) % SPRIME];
110 for(;r != 0; r = r->next)
111 if((type == r->rr.type || type == QTYPE_ANY) && strcasecmp(r->rr.name, host) == 0)
116 int _rr_len(mdnsda rr)
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
122 if(rr->type == QTYPE_PTR) len += 6; // srv record stuff
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;
136 // compare time values easily
137 int _tvdiff(struct timeval old, struct timeval new)
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;
144 // make sure not already on the list, then insert
145 void _r_push(mdnsdr *list, mdnsdr r)
148 for(cur = *list; cur != 0; cur = cur->list)
154 // set this r to probing, set next probe time
155 void _r_probe(mdnsd d, mdnsdr r)
159 // force any r out right away, if valid
160 void _r_publish(mdnsd d, mdnsdr r)
162 if(r->unique && r->unique < 5) return; // probing already
164 d->publish.tv_sec = d->now.tv_sec; d->publish.tv_usec = d->now.tv_usec;
165 _r_push(&d->a_publish,r);
169 void _r_send(mdnsd d, mdnsdr r)
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;
177 { // known unique ones can be sent asap
178 _r_push(&d->a_now,r);
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)
187 d->pause.tv_usec -= 1000000;
189 _r_push(&d->a_pause,r);
192 // create generic unicast response struct
193 void _u_push(mdnsd d, mdnsdr r, int id, unsigned long int to, unsigned short int port)
196 u = (struct unicast *)malloc(sizeof(struct unicast));
197 bzero(u,sizeof(struct unicast));
202 u->next = d->uanswers;
206 void _q_reset(mdnsd d, struct query *q)
208 struct cached *cur = 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;
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;
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;
224 for(cur=d->qlist;cur->list != q;cur = cur->list);
227 if(d->queries[i] == q) d->queries[i] = q->next;
229 for(cur=d->queries[i];cur->next != q;cur = cur->next);
236 void _r_done(mdnsd d, mdnsdr r)
237 { // buh-bye, remove from hash and free
239 int i = _namehash(r->rr.name) % SPRIME;
240 if(d->published[i] == r) d->published[i] = r->next;
242 for(cur=d->published[i];cur && cur->next != r;cur = cur->next);
243 if(cur) cur->next = r->next;
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);
257 void _conflict(mdnsd d, mdnsdr r)
259 r->conflict(r->rr.name,r->rr.type,r->arg);
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;
269 if(d->now.tv_sec >= cur->rr.ttl)
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);
276 free(cur->rr.rdname);
285 // brute force expire any old cached records
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;
294 void _cache(mdnsd d, struct resource *r)
296 struct cached *c = 0;
297 int i = _namehash(r->name) % LPRIME;
299 if(r->class == 32768 + d->class)
301 while((c = _c_next(d,c,r->name,r->type))) c->rr.ttl = 0;
302 _c_expire(d,&d->cache[i]);
307 while((c = _c_next(d,c,r->name,r->type)))
308 if(_a_match(r,&c->rr))
312 _c_expire(d,&d->cache[i]);
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);
327 c->rr.ip = r->known.a.ip;
332 c->rr.rdname = strdup(r->known.ns.name);
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;
341 c->next = d->cache[i];
343 if((c->q = _q_next(d, 0, r->name, r->type)))
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);
355 int _r_out(mdnsd d, struct message *m, mdnsdr *list)
356 { // copy a published record into an outgoing message
359 while((r = *list) != 0 && message_packet_len(m) + _rr_len(&r->rr) < d->frame)
364 message_an(m, r->rr.name, r->rr.type, d->class + 32768, r->rr.ttl);
366 message_an(m, r->rr.name, r->rr.type, d->class, r->rr.ttl);
368 if(r->rr.ttl == 0) _r_done(d,r);
374 mdnsd mdnsd_new(int class, int frame)
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;
386 void mdnsd_shutdown(mdnsd d)
387 { // shutting down, zero out ttl and push out all records
391 for(i=0;i<SPRIME;i++)
392 for(cur = d->published[i]; cur != 0;)
396 cur->list = d->a_now;
403 void mdnsd_flush(mdnsd d)
405 // set all querys to 0 tries
407 // set all mdnsdr to probing
408 // reset all answer lists
411 void mdnsd_free(mdnsd d)
413 // loop through all hashes, free everything
414 // free answers if any
418 char *decode_type (unsigned short 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 "???";
431 void mdnsd_res_dump (FILE *file, struct resource *res)
433 fprintf (file, "%s \"%s\" = ",
434 decode_type (res->type), res->name);
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);
445 fprintf (file, "%s\n", res->known.ns.name);
448 fprintf (file, "%s\n", res->known.cname.name);
451 fprintf (file, "%s\n", res->known.ptr.name);
454 fprintf (file, "%s:%d\n", res->known.srv.name, res->known.srv.port);
457 fprintf (file, "???\n");
461 void mdnsd_dump (FILE *file, struct message *m, char *type)
464 fprintf (file, "==== %s message ====\n", type);
465 if (m->header.qr == 0 && m->qdcount > 0)
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);
474 fprintf (file, "Answers:\n");
475 for (i = 0; i < m->ancount; i++)
477 fprintf (file, " %3d: ", i);
478 mdnsd_res_dump (file, &m->an[i]);
483 fprintf (file, "Authority:\n");
484 for (i = 0; i < m->nscount; i++)
486 fprintf (file, " %3d: ", i);
487 mdnsd_res_dump (file, &m->ns[i]);
492 fprintf (file, "Additional:\n");
493 for (i = 0; i < m->arcount; i++)
495 fprintf (file, " %3d: ", i);
496 mdnsd_res_dump (file, &m->ar[i]);
499 fprintf (file, "\n");
502 void mdnsd_in(mdnsd d, struct message *m, unsigned long int ip, unsigned short int port)
509 if(d->shutdown) return;
511 mdnsd_dump (stderr, m, "incoming");
513 gettimeofday(&d->now,0);
515 if(m->header.qr == 0)
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;
521 // send the matching unicast reply
522 if(port != 5353) _u_push(d,r,m->id,ip,port);
524 for(;r != 0; r = _r_next(d,r,m->qd[i].name,m->qd[i].type))
525 { // check all of our potential answers
527 int may_conflict = 0;
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))
539 if (may_conflict && !have_match)
540 _conflict(d,r); // this answer isn't ours, conflict!
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
548 if(j == m->ancount) _r_send(d,r);
554 for(i=0;i<m->ancount;i++)
555 { // process each answer, check for a conflict, and cache
560 while ((r = _r_next(d,r,m->an[i].name,m->an[i].type)) != 0)
564 if (_a_match(&m->an[i],&r->rr) == 0)
570 if (may_conflict && !have_match)
572 while ((r = _r_next(d,r,m->an[i].name,m->an[i].type)) != 0)
574 if (r->unique && _a_match(&m->an[i],&r->rr) == 0)
582 int mdnsd_out(mdnsd d, struct message *m, unsigned long int *ip, unsigned short int *port)
587 gettimeofday(&d->now,0);
588 bzero(m,sizeof(struct message));
590 // defaults, multicast
592 *ip = inet_addr("224.0.0.251");
597 { // send out individual unicast answers
598 struct unicast *u = d->uanswers;
599 d->uanswers = u->next;
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);
610 //printf("OUT: probing %X now %X pause %X publish %X\n",d->probing,d->a_now,d->a_pause,d->a_publish);
612 // accumulate any immediate responses
613 if(d->a_now) ret += _r_out(d, m, &d->a_now);
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)
623 message_an(m, cur->rr.name, cur->rr.type, d->class + 32768, cur->rr.ttl);
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)
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);
640 d->publish.tv_sec = d->now.tv_sec + 2;
641 d->publish.tv_usec = d->now.tv_usec;
645 // if we're in shutdown, we're done
646 if(d->shutdown) return ret;
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);
651 // now process questions
656 if(d->probing && _tvdiff(d->now,d->probe) <= 0)
659 for(r = d->probing; r != 0;)
660 { // scan probe list to ask questions and process published
662 { // done probing, publish
663 mdnsdr next = r->list;
665 d->probing = r->list;
667 last->list = r->list;
674 message_qd(m, r->rr.name, QTYPE_ANY, d->class);
678 for(r = d->probing; r != 0; last = r, r = r->list)
679 { // scan probe list again to append our to-be answers
681 message_ns(m, r->rr.name, r->rr.type, d->class, r->rr.ttl);
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;
693 if(d->checkqlist && d->now.tv_sec >= d->checkqlist)
694 { // process qlist for retries or expirations
697 unsigned long int nextbest = 0;
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;
706 // include known answers, update questions
707 for(q = d->qlist; q != 0; q = q->list)
709 if(q->nexttry == 0 || q->nexttry > d->now.tv_sec) continue;
711 { // done retrying, expire and reset
712 _c_expire(d,&d->cache[_namehash(q->name) % LPRIME]);
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
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)
724 message_an(m,q->name,q->type,d->class,c->rr.ttl - d->now.tv_sec);
728 d->checkqlist = nextbest;
731 if(d->now.tv_sec > d->expireall)
737 struct timeval *mdnsd_sleep(mdnsd d)
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;
743 // first check for any immediate items to handle
744 if(d->uanswers || d->a_now) return &d->sleep;
746 gettimeofday(&d->now,0);
749 { // then check for paused answers
750 if((usec = _tvdiff(d->now,d->pause)) > 0) d->sleep.tv_usec = usec;
755 { // now check for probe retries
756 if((usec = _tvdiff(d->now,d->probe)) > 0) d->sleep.tv_usec = usec;
761 { // now check for publish retries
762 if((usec = _tvdiff(d->now,d->publish)) > 0) d->sleep.tv_usec = usec;
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;
772 // last resort, next gc expiration
773 if((sec = d->expireall - d->now.tv_sec) > 0) d->sleep.tv_sec = sec;
777 void mdnsd_query(mdnsd d, char *host, int type, int (*answer)(mdnsda a, void *arg), void *arg)
780 struct cached *cur = 0;
781 int i = _namehash(host) % SPRIME;
782 if(!(q = _q_next(d,0,host,type)))
785 q = (struct query *)malloc(sizeof(struct query));
786 bzero(q,sizeof(struct query));
787 q->name = strdup(host);
789 q->next = d->queries[i];
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
795 q->nexttry = d->checkqlist = d->now.tv_sec; // new questin, immediately send out
798 { // no answer means we don't care anymore
806 mdnsda mdnsd_list(mdnsd d, char *host, int type, mdnsda last)
808 return (mdnsda)_c_next(d,(struct cached *)last,host,type);
811 mdnsdr mdnsd_shared(mdnsd d, char *host, int type, long int ttl)
813 int i = _namehash(host) % SPRIME;
815 r = (mdnsdr)malloc(sizeof(struct mdnsdr_struct));
816 bzero(r,sizeof(struct mdnsdr_struct));
817 r->rr.name = strdup(host);
820 r->next = d->published[i];
825 mdnsdr mdnsd_unique(mdnsd d, char *host, int type, long int ttl, void (*conflict)(char *host, int type, void *arg), void *arg)
828 r = mdnsd_shared(d,host,type,ttl);
829 r->conflict = conflict;
832 _r_push(&d->probing,r);
833 d->probe.tv_sec = d->now.tv_sec;
834 d->probe.tv_usec = d->now.tv_usec;
838 void mdnsd_done(mdnsd d, mdnsdr r)
841 if(r->unique && r->unique < 5)
842 { // probing yet, zap from that list first!
843 if(d->probing == r) d->probing = r->list;
845 for(cur=d->probing;cur->list != r;cur = cur->list);
855 void mdnsd_set_raw(mdnsd d, mdnsdr r, char *data, int len)
858 r->rr.rdata = (unsigned char *)malloc(len);
859 memcpy(r->rr.rdata,data,len);
864 void mdnsd_set_host(mdnsd d, mdnsdr r, char *name)
867 r->rr.rdname = strdup(name);
871 void mdnsd_set_ip(mdnsd d, mdnsdr r, unsigned long int ip)
877 void mdnsd_set_srv(mdnsd d, mdnsdr r, int priority, int weight, int port, char *name)
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);