4 // size of query/publish hashes
8 // brute force garbage cleanup frequency, rarely needed (daily default)
11 /* messy, but it's the best/simplest balance I can find at the moment
12 Some internal data types, and a few hashes: querys, answers, cached, and records (published, unique and shared)
13 Each type has different semantics for processing, both for timeouts, incoming, and outgoing I/O
14 They inter-relate too, like records affect the querys they are relevant to
15 Nice things about MDNS: we only publish once (and then ask asked), and only query once, then just expire records we've got cached
22 unsigned long int nexttry;
24 int (*answer)(mdnsda, void *);
26 struct query *next, *list;
33 unsigned short int port;
40 struct mdnsda_struct rr;
47 struct mdnsda_struct rr;
48 char unique; // # of checks performed to ensure
50 void (*conflict)(char *, int, void *);
52 struct mdnsdr_struct *next, *list;
58 unsigned long int expireall, checkqlist;
59 struct timeval now, sleep, pause, probe, publish;
61 struct cached *cache[LPRIME];
62 struct mdnsdr_struct *published[SPRIME], *probing, *a_now, *a_pause, *a_publish;
63 struct unicast *uanswers;
64 struct query *queries[SPRIME], *qlist;
67 int _namehash(const char *s)
69 const unsigned char *name = (const unsigned char *)s;
70 unsigned long h = 0, g;
73 { /* do some fancy bitwanking on the string */
74 h = (h << 4) + (unsigned long)(*name++);
75 if ((g = (h & 0xF0000000UL))!=0)
83 // basic linked list and hash primitives
84 struct query *_q_next(mdnsd d, struct query *q, char *host, int type)
86 if(q == 0) q = d->queries[_namehash(host) % SPRIME];
88 for(;q != 0; q = q->next)
89 if(q->type == type && strcmp(q->name, host) == 0)
93 struct cached *_c_next(mdnsd d, struct cached *c, char *host, int type)
95 if(c == 0) c = d->cache[_namehash(host) % LPRIME];
97 for(;c != 0; c = c->next)
98 if((type == c->rr.type || type == 255) && strcmp(c->rr.name, host) == 0)
102 mdnsdr _r_next(mdnsd d, mdnsdr r, char *host, int type)
104 if(r == 0) r = d->published[_namehash(host) % SPRIME];
106 for(;r != 0; r = r->next)
107 if(type == r->rr.type && strcmp(r->rr.name, host) == 0)
112 int _rr_len(mdnsda rr)
114 int len = 12; // name is always compressed (dup of earlier), plus normal stuff
115 if(rr->rdata) len += rr->rdlen;
116 if(rr->rdname) len += strlen(rr->rdname); // worst case
118 if(rr->type == QTYPE_PTR) len += 6; // srv record stuff
122 int _a_match(struct resource *r, mdnsda a)
123 { // compares new rdata with known a, painfully
124 if(strcmp(r->name,a->name) || r->type != a->type) return 0;
125 if(r->type == QTYPE_SRV && !strcmp(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;
126 if((r->type == QTYPE_PTR || r->type == QTYPE_NS || r->type == QTYPE_CNAME) && !strcmp(a->rdname,r->known.ns.name)) return 1;
127 if(r->rdlength == a->rdlen && !memcmp(r->rdata,a->rdata,r->rdlength)) return 1;
131 // compare time values easily
132 int _tvdiff(struct timeval old, struct timeval new)
135 if(old.tv_sec != new.tv_sec) udiff = (new.tv_sec - old.tv_sec) * 1000000;
136 return (new.tv_usec - old.tv_usec) + udiff;
139 // make sure not already on the list, then insert
140 void _r_push(mdnsdr *list, mdnsdr r)
143 for(cur = *list; cur != 0; cur = cur->list)
149 // set this r to probing, set next probe time
150 void _r_probe(mdnsd d, mdnsdr r)
154 // force any r out right away, if valid
155 void _r_publish(mdnsd d, mdnsdr r)
157 if(r->unique && r->unique < 5) return; // probing already
159 d->publish.tv_sec = d->now.tv_sec; d->publish.tv_usec = d->now.tv_usec;
160 _r_push(&d->a_publish,r);
164 void _r_send(mdnsd d, mdnsdr r)
167 { // being published, make sure that happens soon
168 d->publish.tv_sec = d->now.tv_sec; d->publish.tv_usec = d->now.tv_usec;
172 { // known unique ones can be sent asap
173 _r_push(&d->a_now,r);
176 // set d->pause.tv_usec to random 20-120 msec
177 d->pause.tv_sec = d->now.tv_sec;
178 d->pause.tv_usec = d->now.tv_usec + (d->now.tv_usec % 100) + 20;
179 _r_push(&d->a_pause,r);
182 // create generic unicast response struct
183 void _u_push(mdnsd d, mdnsdr r, int id, unsigned long int to, unsigned short int port)
186 u = (struct unicast *)malloc(sizeof(struct unicast));
187 bzero(u,sizeof(struct unicast));
192 u->next = d->uanswers;
196 void _q_reset(mdnsd d, struct query *q)
198 struct cached *cur = 0;
201 while(cur = _c_next(d,cur,q->name,q->type))
202 if(q->nexttry == 0 || cur->rr.ttl - 7 < q->nexttry) q->nexttry = cur->rr.ttl - 7;
203 if(q->nexttry != 0 && q->nexttry < d->checkqlist) d->checkqlist = q->nexttry;
206 void _q_done(mdnsd d, struct query *q)
207 { // no more query, update all it's cached entries, remove from lists
208 struct cached *c = 0;
210 int i = _namehash(q->name) % LPRIME;
211 while(c = _c_next(d,c,q->name,q->type)) c->q = 0;
212 if(d->qlist == q) d->qlist = q->list;
214 for(cur=d->qlist;cur->list != q;cur = cur->list);
217 if(d->queries[i] == q) d->queries[i] = q->next;
219 for(cur=d->queries[i];cur->next != q;cur = cur->next);
226 void _r_done(mdnsd d, mdnsdr r)
227 { // buh-bye, remove from hash and free
229 int i = _namehash(r->rr.name) % SPRIME;
230 if(d->published[i] == r) d->published[i] = r->next;
232 for(cur=d->published[i];cur && cur->next != r;cur = cur->next);
233 if(cur) cur->next = r->next;
241 void _q_answer(mdnsd d, struct cached *c)
242 { // call the answer function with this cached entry
243 if(c->rr.ttl <= d->now.tv_sec) c->rr.ttl = 0;
244 if(c->q->answer(&c->rr,c->q->arg) == -1) _q_done(d, c->q);
247 void _conflict(mdnsd d, mdnsdr r)
249 r->conflict(r->rr.name,r->rr.type,r->arg);
253 void _c_expire(mdnsd d, struct cached **list)
254 { // expire any old entries in this list
255 struct cached *next, *cur = *list, *last = 0;
259 if(d->now.tv_sec >= cur->rr.ttl)
261 if(last) last->next = next;
262 if(*list == cur) *list = next; // update list pointer if the first one expired
263 if(cur->q) _q_answer(d,cur);
266 free(cur->rr.rdname);
275 // brute force expire any old cached records
279 for(i=0;i<LPRIME;i++)
280 if(d->cache[i]) _c_expire(d,&d->cache[i]);
281 d->expireall = d->now.tv_sec + GC;
284 void _cache(mdnsd d, struct resource *r)
286 struct cached *c = 0;
287 int i = _namehash(r->name) % LPRIME;
289 if(r->class == 32768 + d->class)
291 while(c = _c_next(d,c,r->name,r->type)) c->rr.ttl = 0;
292 _c_expire(d,&d->cache[i]);
297 while(c = _c_next(d,c,r->name,r->type))
298 if(_a_match(r,&c->rr))
301 _c_expire(d,&d->cache[i]);
306 c = (struct cached *)malloc(sizeof(struct cached));
307 bzero(c,sizeof(struct cached));
308 c->rr.name = strdup(r->name);
309 c->rr.type = r->type;
310 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
311 c->rr.rdlen = r->rdlength;
312 c->rr.rdata = (unsigned char *)malloc(r->rdlength);
313 memcpy(c->rr.rdata,r->rdata,r->rdlength);
317 c->rr.ip = r->known.a.ip;
322 c->rr.rdname = strdup(r->known.ns.name);
325 c->rr.rdname = strdup(r->known.srv.name);
326 c->rr.srv.port = r->known.srv.port;
327 c->rr.srv.weight = r->known.srv.weight;
328 c->rr.srv.priority = r->known.srv.priority;
331 c->next = d->cache[i];
333 if(c->q = _q_next(d, 0, r->name, r->type))
337 void _a_copy(struct message *m, mdnsda a)
338 { // copy the data bits only
339 if(a->rdata) { message_rdata_raw(m, a->rdata, a->rdlen); return; }
340 if(a->ip) message_rdata_long(m, a->ip);
341 if(a->type == QTYPE_SRV) message_rdata_srv(m, a->srv.priority, a->srv.weight, a->srv.port, a->rdname);
342 else if(a->rdname) message_rdata_name(m, a->rdname);
345 int _r_out(mdnsd d, struct message *m, mdnsdr *list)
346 { // copy a published record into an outgoing message
349 while((r = *list) != 0 && message_packet_len(m) + _rr_len(&r->rr) < d->frame)
354 message_an(m, r->rr.name, r->rr.type, d->class + 32768, r->rr.ttl);
356 message_an(m, r->rr.name, r->rr.type, d->class, r->rr.ttl);
358 if(r->rr.ttl == 0) _r_done(d,r);
364 mdnsd mdnsd_new(int class, int frame)
368 d = (mdnsd)malloc(sizeof(struct mdnsd_struct));
369 bzero(d,sizeof(struct mdnsd_struct));
370 gettimeofday(&d->now,0);
371 d->expireall = d->now.tv_sec + GC;
377 void mdnsd_shutdown(mdnsd d)
378 { // shutting down, zero out ttl and push out all records
382 for(i=0;i<SPRIME;i++)
383 for(cur = d->published[i]; cur != 0;)
387 cur->list = d->a_now;
394 void mdnsd_flush(mdnsd d)
396 // set all querys to 0 tries
398 // set all mdnsdr to probing
399 // reset all answer lists
402 void mdnsd_free(mdnsd d)
405 // loop through all hashes, free everything
406 // free answers if any
410 void mdnsd_in(mdnsd d, struct message *m, unsigned long int ip, unsigned short int port)
415 if(d->shutdown) return;
417 gettimeofday(&d->now,0);
419 if(m->header.qr == 0)
421 for(i=0;i<m->qdcount;i++)
422 { // process each query
423 if(m->qd[i].class != d->class || (r = _r_next(d,0,m->qd[i].name,m->qd[i].type)) == 0) continue;
425 // send the matching unicast reply
426 if(port != 5353) _u_push(d,r,m->id,ip,port);
428 for(;r != 0; r = _r_next(d,r,m->qd[i].name,m->qd[i].type))
429 { // check all of our potential answers
430 if(r->unique && r->unique < 5)
431 { // probing state, check for conflicts
432 for(j=0;j<m->nscount;j++)
433 { // check all to-be answers against our own
434 if(m->qd[i].type != m->an[j].type || strcmp(m->qd[i].name,m->an[j].name)) continue;
435 if(!_a_match(&m->an[j],&r->rr)) _conflict(d,r); // this answer isn't ours, conflict!
439 for(j=0;j<m->ancount;j++)
440 { // check the known answers for this question
441 if(m->qd[i].type != m->an[j].type || strcmp(m->qd[i].name,m->an[j].name)) continue;
442 if(_a_match(&m->an[j],&r->rr)) break; // they already have this answer
444 if(j == m->ancount) _r_send(d,r);
450 for(i=0;i<m->ancount;i++)
451 { // process each answer, check for a conflict, and cache
452 if((r = _r_next(d,0,m->an[i].name,m->an[i].type)) != 0 && r->unique && _a_match(&m->an[i],&r->rr) == 0) _conflict(d,r);
457 int mdnsd_out(mdnsd d, struct message *m, unsigned long int *ip, unsigned short int *port)
462 gettimeofday(&d->now,0);
463 bzero(m,sizeof(struct message));
465 // defaults, multicast
467 *ip = inet_addr("224.0.0.251");
472 { // send out individual unicast answers
473 struct unicast *u = d->uanswers;
474 d->uanswers = u->next;
478 message_qd(m, u->r->rr.name, u->r->rr.type, d->class);
479 message_an(m, u->r->rr.name, u->r->rr.type, d->class, u->r->rr.ttl);
480 _a_copy(m, &u->r->rr);
485 //printf("OUT: probing %X now %X pause %X publish %X\n",d->probing,d->a_now,d->a_pause,d->a_publish);
487 // accumulate any immediate responses
488 if(d->a_now) ret += _r_out(d, m, &d->a_now);
490 if(d->a_publish && _tvdiff(d->now,d->publish) <= 0)
491 { // check to see if it's time to send the publish retries (and unlink if done)
492 mdnsdr next, cur = d->a_publish, last = 0;
493 while(cur && message_packet_len(m) + _rr_len(&cur->rr) < d->frame)
498 message_an(m, cur->rr.name, cur->rr.type, d->class + 32768, cur->rr.ttl);
500 message_an(m, cur->rr.name, cur->rr.type, d->class, cur->rr.ttl);
501 _a_copy(m, &cur->rr);
502 if(cur->rr.ttl != 0 && cur->tries < 4)
508 if(d->a_publish == cur) d->a_publish = next;
509 if(last) last->list = next;
510 if(cur->rr.ttl == 0) _r_done(d,cur);
515 d->publish.tv_sec = d->now.tv_sec + 2;
516 d->publish.tv_usec = d->now.tv_usec;
520 // if we're in shutdown, we're done
521 if(d->shutdown) return ret;
523 // check if a_pause is ready
524 if(d->a_pause && _tvdiff(d->now, d->pause) <= 0) ret += _r_out(d, m, &d->a_pause);
526 // now process questions
531 if(d->probing && _tvdiff(d->now,d->probe) <= 0)
534 for(r = d->probing; r != 0;)
535 { // scan probe list to ask questions and process published
537 { // done probing, publish
538 mdnsdr next = r->list;
540 d->probing = r->list;
542 last->list = r->list;
549 message_qd(m, r->rr.name, r->rr.type, d->class);
553 for(r = d->probing; r != 0; last = r, r = r->list)
554 { // scan probe list again to append our to-be answers
556 message_ns(m, r->rr.name, r->rr.type, d->class, r->rr.ttl);
561 { // process probes again in the future
562 d->probe.tv_sec = d->now.tv_sec;
563 d->probe.tv_usec = d->now.tv_usec + 250000;
568 if(d->checkqlist && d->now.tv_sec >= d->checkqlist)
569 { // process qlist for retries or expirations
572 unsigned long int nextbest = 0;
574 // ask questions first, track nextbest time
575 for(q = d->qlist; q != 0; q = q->list)
576 if(q->nexttry > 0 && q->nexttry <= d->now.tv_sec && q->tries < 3)
577 message_qd(m,q->name,q->type,d->class);
578 else if(q->nexttry > 0 && (nextbest == 0 || q->nexttry < nextbest))
579 nextbest = q->nexttry;
581 // include known answers, update questions
582 for(q = d->qlist; q != 0; q = q->list)
584 if(q->nexttry == 0 || q->nexttry > d->now.tv_sec) continue;
586 { // done retrying, expire and reset
587 _c_expire(d,&d->cache[_namehash(q->name) % LPRIME]);
592 q->nexttry = d->now.tv_sec + ++q->tries;
593 if(nextbest == 0 || q->nexttry < nextbest)
594 nextbest = q->nexttry;
595 // if room, add all known good entries
597 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)
599 message_an(m,q->name,q->type,d->class,c->rr.ttl - d->now.tv_sec);
603 d->checkqlist = nextbest;
606 if(d->now.tv_sec > d->expireall)
612 struct timeval *mdnsd_sleep(mdnsd d)
616 d->sleep.tv_sec = d->sleep.tv_usec = 0;
617 #define RET while(d->sleep.tv_usec > 1000000) {d->sleep.tv_sec++;d->sleep.tv_usec -= 1000000;} return &d->sleep;
619 // first check for any immediate items to handle
620 if(d->uanswers || d->a_now) return &d->sleep;
622 gettimeofday(&d->now,0);
625 { // then check for paused answers
626 if((usec = _tvdiff(d->now,d->pause)) > 0) d->sleep.tv_usec = usec;
631 { // now check for probe retries
632 if((usec = _tvdiff(d->now,d->probe)) > 0) d->sleep.tv_usec = usec;
637 { // now check for publish retries
638 if((usec = _tvdiff(d->now,d->publish)) > 0) d->sleep.tv_usec = usec;
643 { // also check for queries with known answer expiration/retry
644 if((sec = d->checkqlist - d->now.tv_sec) > 0) d->sleep.tv_sec = sec;
648 // last resort, next gc expiration
649 if((sec = d->expireall - d->now.tv_sec) > 0) d->sleep.tv_sec = sec;
653 void mdnsd_query(mdnsd d, char *host, int type, int (*answer)(mdnsda a, void *arg), void *arg)
656 struct cached *cur = 0;
657 int i = _namehash(host) % SPRIME;
658 if(!(q = _q_next(d,0,host,type)))
661 q = (struct query *)malloc(sizeof(struct query));
662 bzero(q,sizeof(struct query));
663 q->name = strdup(host);
665 q->next = d->queries[i];
667 d->qlist = d->queries[i] = q;
668 while(cur = _c_next(d,cur,q->name,q->type))
669 cur->q = q; // any cached entries should be associated
671 q->nexttry = d->checkqlist = d->now.tv_sec; // new questin, immediately send out
674 { // no answer means we don't care anymore
682 mdnsda mdnsd_list(mdnsd d, char *host, int type, mdnsda last)
684 return (mdnsda)_c_next(d,(struct cached *)last,host,type);
687 mdnsdr mdnsd_shared(mdnsd d, char *host, int type, long int ttl)
689 int i = _namehash(host) % SPRIME;
691 r = (mdnsdr)malloc(sizeof(struct mdnsdr_struct));
692 bzero(r,sizeof(struct mdnsdr_struct));
693 r->rr.name = strdup(host);
696 r->next = d->published[i];
701 mdnsdr mdnsd_unique(mdnsd d, char *host, int type, long int ttl, void (*conflict)(char *host, int type, void *arg), void *arg)
704 r = mdnsd_shared(d,host,type,ttl);
705 r->conflict = conflict;
708 _r_push(&d->probing,r);
709 d->probe.tv_sec = d->now.tv_sec;
710 d->probe.tv_usec = d->now.tv_usec;
714 void mdnsd_done(mdnsd d, mdnsdr r)
717 if(r->unique && r->unique < 5)
718 { // probing yet, zap from that list first!
719 if(d->probing == r) d->probing = r->list;
721 for(cur=d->probing;cur->list != r;cur = cur->list);
731 void mdnsd_set_raw(mdnsd d, mdnsdr r, char *data, int len)
734 r->rr.rdata = (unsigned char *)malloc(len);
735 memcpy(r->rr.rdata,data,len);
740 void mdnsd_set_host(mdnsd d, mdnsdr r, char *name)
743 r->rr.rdname = strdup(name);
747 void mdnsd_set_ip(mdnsd d, mdnsdr r, unsigned long int ip)
753 void mdnsd_set_srv(mdnsd d, mdnsdr r, int priority, int weight, int port, char *name)
755 r->rr.srv.priority = priority;
756 r->rr.srv.weight = weight;
757 r->rr.srv.port = port;
758 mdnsd_set_host(d,r,name);