]> git.meshlink.io Git - catta/blob - libavahi-core/psched.c
update todo
[catta] / libavahi-core / psched.c
1 /* $Id$ */
2
3 /***
4   This file is part of avahi.
5  
6   avahi is free software; you can redistribute it and/or modify it
7   under the terms of the GNU Lesser General Public License as
8   published by the Free Software Foundation; either version 2.1 of the
9   License, or (at your option) any later version.
10  
11   avahi is distributed in the hope that it will be useful, but WITHOUT
12   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13   or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
14   Public License for more details.
15  
16   You should have received a copy of the GNU Lesser General Public
17   License along with avahi; if not, write to the Free Software
18   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
19   USA.
20 ***/
21
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25
26 #include <string.h>
27
28 #include "util.h"
29 #include "psched.h"
30
31 #define AVAHI_QUERY_HISTORY_MSEC 100
32 #define AVAHI_QUERY_DEFER_MSEC 100
33 #define AVAHI_RESPONSE_HISTORY_MSEC 700
34 #define AVAHI_RESPONSE_DEFER_MSEC 20
35 #define AVAHI_RESPONSE_JITTER_MSEC 100
36 #define AVAHI_PROBE_DEFER_MSEC 70
37
38 AvahiPacketScheduler *avahi_packet_scheduler_new(AvahiServer *server, AvahiInterface *i) {
39     AvahiPacketScheduler *s;
40
41     g_assert(server);
42     g_assert(i);
43
44     s = g_new(AvahiPacketScheduler, 1);
45     s->server = server;
46     s->interface = i;
47
48     AVAHI_LLIST_HEAD_INIT(AvahiQueryJob, s->query_jobs);
49     AVAHI_LLIST_HEAD_INIT(AvahiResponseJob, s->response_jobs);
50     AVAHI_LLIST_HEAD_INIT(AvahiKnownAnswer, s->known_answers);
51     AVAHI_LLIST_HEAD_INIT(AvahiProbeJob, s->probe_jobs);
52     
53     return s;
54 }
55
56 static void query_job_free(AvahiPacketScheduler *s, AvahiQueryJob *qj) {
57     g_assert(qj);
58
59     if (qj->time_event)
60         avahi_time_event_queue_remove(qj->scheduler->server->time_event_queue, qj->time_event);
61
62     AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->query_jobs, qj);
63     
64     avahi_key_unref(qj->key);
65     g_free(qj);
66 }
67
68 static void response_job_free(AvahiPacketScheduler *s, AvahiResponseJob *rj) {
69     g_assert(rj);
70
71     if (rj->time_event)
72         avahi_time_event_queue_remove(rj->scheduler->server->time_event_queue, rj->time_event);
73
74     AVAHI_LLIST_REMOVE(AvahiResponseJob, jobs, s->response_jobs, rj);
75
76     avahi_record_unref(rj->record);
77     g_free(rj);
78 }
79
80 static void probe_job_free(AvahiPacketScheduler *s, AvahiProbeJob *pj) {
81     g_assert(pj);
82
83     if (pj->time_event)
84         avahi_time_event_queue_remove(pj->scheduler->server->time_event_queue, pj->time_event);
85
86     AVAHI_LLIST_REMOVE(AvahiProbeJob, jobs, s->probe_jobs, pj);
87
88     avahi_record_unref(pj->record);
89     g_free(pj);
90 }
91
92 void avahi_packet_scheduler_free(AvahiPacketScheduler *s) {
93     AvahiQueryJob *qj;
94     AvahiResponseJob *rj;
95     AvahiProbeJob *pj;
96
97     g_assert(s);
98
99     g_assert(!s->known_answers);
100     
101     while ((qj = s->query_jobs))
102         query_job_free(s, qj);
103     while ((rj = s->response_jobs))
104         response_job_free(s, rj);
105     while ((pj = s->probe_jobs))
106         probe_job_free(s, pj);
107
108     g_free(s);
109 }
110
111 static gpointer known_answer_walk_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, gpointer userdata) {
112     AvahiPacketScheduler *s = userdata;
113     AvahiKnownAnswer *ka;
114     
115     g_assert(c);
116     g_assert(pattern);
117     g_assert(e);
118     g_assert(s);
119
120     if (avahi_cache_entry_half_ttl(c, e))
121         return NULL;
122     
123     ka = g_new0(AvahiKnownAnswer, 1);
124     ka->scheduler = s;
125     ka->record = avahi_record_ref(e->record);
126
127     AVAHI_LLIST_PREPEND(AvahiKnownAnswer, known_answer, s->known_answers, ka);
128     return NULL;
129 }
130
131 static guint8* packet_add_query_job(AvahiPacketScheduler *s, AvahiDnsPacket *p, AvahiQueryJob *qj) {
132     guint8 *d;
133
134     g_assert(s);
135     g_assert(p);
136     g_assert(qj);
137
138     if ((d = avahi_dns_packet_append_key(p, qj->key, FALSE))) {
139         GTimeVal tv;
140
141         qj->done = 1;
142
143         /* Drop query after some time from history */
144         avahi_elapse_time(&tv, AVAHI_QUERY_HISTORY_MSEC, 0);
145         avahi_time_event_queue_update(s->server->time_event_queue, qj->time_event, &tv);
146
147         g_get_current_time(&qj->delivery);
148
149         /* Add all matching known answers to the list */
150         avahi_cache_walk(s->interface->cache, qj->key, known_answer_walk_callback, s);
151     }
152
153     return d;
154 }
155
156 static void append_known_answers_and_send(AvahiPacketScheduler *s, AvahiDnsPacket *p) {
157     AvahiKnownAnswer *ka;
158     guint n;
159     g_assert(s);
160     g_assert(p);
161
162     n = 0;
163     
164     while ((ka = s->known_answers)) {
165
166         while (!avahi_dns_packet_append_record(p, ka->record, FALSE)) {
167
168             g_assert(!avahi_dns_packet_is_empty(p));
169
170             avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_FLAGS, avahi_dns_packet_get_field(p, AVAHI_DNS_FIELD_FLAGS) | AVAHI_DNS_FLAG_TC);
171             avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_ANCOUNT, n);
172             avahi_interface_send_packet(s->interface, p);
173             avahi_dns_packet_free(p);
174
175             p = avahi_dns_packet_new_query(s->interface->hardware->mtu - 48);
176             n = 0;
177         }
178
179         AVAHI_LLIST_REMOVE(AvahiKnownAnswer, known_answer, s->known_answers, ka);
180         avahi_record_unref(ka->record);
181         g_free(ka);
182         
183         n++;
184     }
185     
186     avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_ANCOUNT, n);
187     avahi_interface_send_packet(s->interface, p);
188     avahi_dns_packet_free(p);
189 }
190
191 static void query_elapse(AvahiTimeEvent *e, gpointer data) {
192     AvahiQueryJob *qj = data;
193     AvahiPacketScheduler *s;
194     AvahiDnsPacket *p;
195     guint n;
196     guint8 *d;
197
198     g_assert(qj);
199     s = qj->scheduler;
200
201     if (qj->done) {
202         /* Lets remove it  from the history */
203         query_job_free(s, qj);
204         return;
205     }
206
207     g_assert(!s->known_answers);
208     
209     p = avahi_dns_packet_new_query(s->interface->hardware->mtu - 48);
210     d = packet_add_query_job(s, p, qj);
211     g_assert(d);
212     n = 1;
213
214     /* Try to fill up packet with more queries, if available */
215     for (qj = s->query_jobs; qj; qj = qj->jobs_next) {
216
217         if (qj->done)
218             continue;
219
220         if (!packet_add_query_job(s, p, qj))
221             break;
222
223         n++;
224     }
225
226     avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_QDCOUNT, n);
227
228     /* Now add known answers */
229     append_known_answers_and_send(s, p);
230 }
231
232 AvahiQueryJob* query_job_new(AvahiPacketScheduler *s, AvahiKey *key) {
233     AvahiQueryJob *qj;
234     
235     g_assert(s);
236     g_assert(key);
237
238     qj = g_new(AvahiQueryJob, 1);
239     qj->scheduler = s;
240     qj->key = avahi_key_ref(key);
241     qj->done = FALSE;
242     qj->time_event = NULL;
243     
244     AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->query_jobs, qj);
245
246     return qj;
247 }
248
249 void avahi_packet_scheduler_post_query(AvahiPacketScheduler *s, AvahiKey *key, gboolean immediately) {
250     GTimeVal tv;
251     AvahiQueryJob *qj;
252     
253     g_assert(s);
254     g_assert(key);
255
256     avahi_elapse_time(&tv, immediately ? 0 : AVAHI_QUERY_DEFER_MSEC, 0);
257
258     for (qj = s->query_jobs; qj; qj = qj->jobs_next) {
259
260         if (avahi_key_equal(qj->key, key)) {
261
262             glong d = avahi_timeval_diff(&tv, &qj->delivery);
263
264             /* Duplicate questions suppression */
265             if (d >= 0 && d <= AVAHI_QUERY_HISTORY_MSEC*1000) {
266                 g_message("WARNING! DUPLICATE QUERY SUPPRESSION ACTIVE!");
267                 return;
268             }
269             
270             query_job_free(s, qj);
271             break;
272         }
273
274     }
275     
276     qj = query_job_new(s, key);
277     qj->delivery = tv;
278     qj->time_event = avahi_time_event_queue_add(s->server->time_event_queue, &qj->delivery, query_elapse, qj);
279 }
280
281 static guint8* packet_add_response_job(AvahiPacketScheduler *s, AvahiDnsPacket *p, AvahiResponseJob *rj) {
282     guint8 *d;
283
284     g_assert(s);
285     g_assert(p);
286     g_assert(rj);
287
288     if ((d = avahi_dns_packet_append_record(p, rj->record, rj->flush_cache))) {
289         GTimeVal tv;
290
291         rj->done = 1;
292
293         /* Drop response after some time from history */
294         avahi_elapse_time(&tv, AVAHI_RESPONSE_HISTORY_MSEC, 0);
295         avahi_time_event_queue_update(s->server->time_event_queue, rj->time_event, &tv);
296
297         g_get_current_time(&rj->delivery);
298     }
299
300     return d;
301 }
302
303 static void send_response_packet(AvahiPacketScheduler *s, AvahiResponseJob *rj) {
304     AvahiDnsPacket *p;
305     guint n;
306
307     g_assert(s);
308
309     p = avahi_dns_packet_new_response(s->interface->hardware->mtu - 200);
310     n = 0;
311
312     /* If a job was specified, put it in the packet. */
313     if (rj) {
314         guint8 *d;
315         d = packet_add_response_job(s, p, rj);
316         g_assert(d);
317         n++;
318     }
319
320     /* Try to fill up packet with more responses, if available */
321     for (rj = s->response_jobs; rj; rj = rj->jobs_next) {
322
323         if (rj->done)
324             continue;
325
326         if (!packet_add_response_job(s, p, rj))
327             break;
328
329         n++;
330     }
331
332     avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_ANCOUNT, n);
333     avahi_interface_send_packet(s->interface, p);
334     avahi_dns_packet_free(p);
335 }
336
337 static void response_elapse(AvahiTimeEvent *e, gpointer data) {
338     AvahiResponseJob *rj = data;
339     AvahiPacketScheduler *s;
340
341     g_assert(rj);
342     s = rj->scheduler;
343
344     if (rj->done) {
345         /* Lets remove it  from the history */
346         response_job_free(s, rj);
347         return;
348     }
349
350     send_response_packet(s, rj);
351 }
352
353 static AvahiResponseJob* look_for_response(AvahiPacketScheduler *s, AvahiRecord *record) {
354     AvahiResponseJob *rj;
355
356     g_assert(s);
357     g_assert(record);
358
359     for (rj = s->response_jobs; rj; rj = rj->jobs_next)
360         if (avahi_record_equal_no_ttl(rj->record, record))
361             return rj;
362
363     return NULL;
364 }
365
366 static AvahiResponseJob* response_job_new(AvahiPacketScheduler *s, AvahiRecord *record) {
367     AvahiResponseJob *rj;
368     
369     g_assert(s);
370     g_assert(record);
371
372     rj = g_new(AvahiResponseJob, 1);
373     rj->scheduler = s;
374     rj->record = avahi_record_ref(record);
375     rj->done = FALSE;
376     rj->time_event = NULL;
377     rj->address_valid = FALSE;
378     rj->flush_cache = FALSE;
379     
380     AVAHI_LLIST_PREPEND(AvahiResponseJob, jobs, s->response_jobs, rj);
381
382     return rj;
383 }
384
385 void avahi_packet_scheduler_post_response(AvahiPacketScheduler *s, const AvahiAddress *a, AvahiRecord *record, gboolean flush_cache, gboolean immediately) {
386     AvahiResponseJob *rj;
387     GTimeVal tv;
388     
389     g_assert(s);
390     g_assert(record);
391
392     g_assert(!avahi_key_is_pattern(record->key));
393     
394     avahi_elapse_time(&tv, immediately ? 0 : AVAHI_RESPONSE_DEFER_MSEC, immediately ? 0 : AVAHI_RESPONSE_JITTER_MSEC);
395     
396     /* Don't send out duplicates */
397     
398     if ((rj = look_for_response(s, record))) {
399         glong d;
400
401         d = avahi_timeval_diff(&tv, &rj->delivery);
402         
403         /* If there's already a matching packet in our history or in
404          * the schedule, we do nothing. */
405         if (!!record->ttl == !!rj->record->ttl &&
406             d >= 0 && d <= AVAHI_RESPONSE_HISTORY_MSEC*1000) {
407             g_message("WARNING! DUPLICATE RESPONSE SUPPRESSION ACTIVE!");
408
409             /* This job is no longer specific to a single querier, so
410              * make sure it isn't suppressed by known answer
411              * suppresion */
412
413             if (rj->address_valid && (!a || avahi_address_cmp(a, &rj->address) != 0))
414                 rj->address_valid = FALSE;
415
416             rj->flush_cache = flush_cache;
417             
418             return;
419         }
420
421         /* Either one was a goodbye packet, but the other was not, so
422          * let's drop the older one. */
423         response_job_free(s, rj);
424     }
425
426 /*     g_message("ACCEPTED NEW RESPONSE [%s]", t = avahi_record_to_string(record)); */
427 /*     g_free(t); */
428
429     /* Create a new job and schedule it */
430     rj = response_job_new(s, record);
431     rj->flush_cache = flush_cache;
432     rj->delivery = tv;
433     rj->time_event = avahi_time_event_queue_add(s->server->time_event_queue, &rj->delivery, response_elapse, rj);
434
435     /* Store the address of the host this messages is intended to, so
436        that we can drop this job in case a truncated message with
437        known answer suppresion entries is recieved */
438
439     if ((rj->address_valid = !!a))
440         rj->address = *a;
441 }
442
443 void avahi_packet_scheduler_incoming_query(AvahiPacketScheduler *s, AvahiKey *key) {
444     GTimeVal tv;
445     AvahiQueryJob *qj;
446     
447     g_assert(s);
448     g_assert(key);
449
450     /* This function is called whenever an incoming query was
451      * receieved. We drop all scheduled queries which match here. The
452      * keyword is "DUPLICATE QUESTION SUPPRESION". */
453
454     for (qj = s->query_jobs; qj; qj = qj->jobs_next)
455         if (avahi_key_equal(qj->key, key)) {
456
457             if (qj->done)
458                 return;
459
460             goto mark_done;
461         }
462
463
464     /* No matching job was found. Add the query to the history */
465     qj = query_job_new(s, key);
466
467 mark_done:
468     qj->done = TRUE;
469
470     /* Drop the query after some time */
471     avahi_elapse_time(&tv, AVAHI_QUERY_HISTORY_MSEC, 0);
472     qj->time_event = avahi_time_event_queue_add(s->server->time_event_queue, &tv, query_elapse, qj);
473
474     g_get_current_time(&qj->delivery);
475 }
476
477 void response_job_set_elapse_time(AvahiPacketScheduler *s, AvahiResponseJob *rj, guint msec, guint jitter) {
478     GTimeVal tv;
479
480     g_assert(s);
481     g_assert(rj);
482
483     avahi_elapse_time(&tv, msec, jitter);
484
485     if (rj->time_event)
486         avahi_time_event_queue_update(s->server->time_event_queue, rj->time_event, &tv);
487     else
488         rj->time_event = avahi_time_event_queue_add(s->server->time_event_queue, &tv, response_elapse, rj);
489     
490 }
491
492 void avahi_packet_scheduler_incoming_response(AvahiPacketScheduler *s, AvahiRecord *record) {
493     AvahiResponseJob *rj;
494     
495     g_assert(s);
496     g_assert(record);
497
498     /* This function is called whenever an incoming response was
499      * receieved. We drop all scheduled responses which match
500      * here. The keyword is "DUPLICATE ANSWER SUPPRESION". */
501     
502     for (rj = s->response_jobs; rj; rj = rj->jobs_next)
503         if (avahi_record_equal_no_ttl(rj->record, record)) {
504
505             if (rj->done) {
506
507                 if (!!record->ttl == !!rj->record->ttl) {
508                     /* An entry like this is already in our history,
509                      * so let's get out of here! */
510                     
511                     return;
512                     
513                 } else {
514                     /* Either one was a goodbye packet but other was
515                      * none. We remove the history entry, and add a
516                      * new one */
517                     
518                     response_job_free(s, rj);
519                     break;
520                 }
521         
522             } else {
523
524                 if (!!record->ttl == !!rj->record->ttl) {
525
526                     /* The incoming packet matches our scheduled
527                      * record, so let's mark that one as done */
528
529                     goto mark_done;
530                     
531                 } else {
532
533                     /* Either one was a goodbye packet but other was
534                      * none. We ignore the incoming packet. */
535
536                     return;
537                 }
538             }
539         }
540
541     /* No matching job was found. Add the query to the history */
542     rj = response_job_new(s, record);
543
544 mark_done:
545     rj->done = TRUE;
546                     
547     /* Drop response after 500ms from history */
548     response_job_set_elapse_time(s, rj, AVAHI_RESPONSE_HISTORY_MSEC, 0);
549
550     g_get_current_time(&rj->delivery);
551 }
552
553 void avahi_packet_scheduler_incoming_known_answer(AvahiPacketScheduler *s, AvahiRecord *record, const AvahiAddress *a) {
554     AvahiResponseJob *rj;
555     
556     g_assert(s);
557     g_assert(record);
558     g_assert(a);
559
560     for (rj = s->response_jobs; rj; rj = rj->jobs_next) {
561
562         g_assert(record->ttl > 0);
563         g_assert(rj->record->ttl/2);
564         
565         if (avahi_record_equal_no_ttl(rj->record, record))
566             if (rj->address_valid)
567                 if (avahi_address_cmp(&rj->address, a))
568                     if (record->ttl >= rj->record->ttl/2) {
569
570             /* Let's suppress it */
571
572             response_job_free(s, rj);
573             break;
574         }
575     }
576 }
577
578 void avahi_packet_scheduler_flush_responses(AvahiPacketScheduler *s) {
579     AvahiResponseJob *rj;
580     
581     g_assert(s);
582
583     /* Send all scheduled responses, ignoring the scheduled time */
584     
585     for (rj = s->response_jobs; rj; rj = rj->jobs_next)
586         if (!rj->done)
587             send_response_packet(s, rj);
588 }
589
590 static AvahiProbeJob* probe_job_new(AvahiPacketScheduler *s, AvahiRecord *record) {
591     AvahiProbeJob *pj;
592     
593     g_assert(s);
594     g_assert(record);
595
596     pj = g_new(AvahiProbeJob, 1);
597     pj->scheduler = s;
598     pj->record = avahi_record_ref(record);
599     pj->time_event = NULL;
600     pj->chosen = FALSE;
601     
602     AVAHI_LLIST_PREPEND(AvahiProbeJob, jobs, s->probe_jobs, pj);
603
604     return pj;
605 }
606
607 static guint8* packet_add_probe_query(AvahiPacketScheduler *s, AvahiDnsPacket *p, AvahiProbeJob *pj) {
608     guint size;
609     guint8 *ret;
610     AvahiKey *k;
611
612     g_assert(s);
613     g_assert(p);
614     g_assert(pj);
615
616     g_assert(!pj->chosen);
617     
618     /* Estimate the size for this record */
619     size =
620         avahi_key_get_estimate_size(pj->record->key) +
621         avahi_record_get_estimate_size(pj->record);
622
623     /* Too large */
624     if (size > avahi_dns_packet_space(p))
625         return NULL;
626
627     /* Create the probe query */
628     k = avahi_key_new(pj->record->key->name, pj->record->key->class, AVAHI_DNS_TYPE_ANY);
629     ret = avahi_dns_packet_append_key(p, k, FALSE);
630     g_assert(ret);
631
632     /* Mark this job for addition to the packet */
633     pj->chosen = TRUE;
634
635     /* Scan for more jobs whith matching key pattern */
636     for (pj = s->probe_jobs; pj; pj = pj->jobs_next) {
637         if (pj->chosen)
638             continue;
639
640         /* Does the record match the probe? */
641         if (k->class != pj->record->key->class || !avahi_domain_equal(k->name, pj->record->key->name))
642             continue;
643         
644         /* This job wouldn't fit in */
645         if (avahi_record_get_estimate_size(pj->record) > avahi_dns_packet_space(p))
646             break;
647
648         /* Mark this job for addition to the packet */
649         pj->chosen = TRUE;
650     }
651
652     avahi_key_unref(k);
653             
654     return ret;
655 }
656
657 static void probe_elapse(AvahiTimeEvent *e, gpointer data) {
658     AvahiProbeJob *pj = data, *next;
659     AvahiPacketScheduler *s;
660     AvahiDnsPacket *p;
661     guint n;
662
663     g_assert(pj);
664     s = pj->scheduler;
665
666     p = avahi_dns_packet_new_query(s->interface->hardware->mtu - 48);
667
668     /* Add the import probe */
669     if (!packet_add_probe_query(s, p, pj)) {
670         g_warning("Record too large! ---");
671         avahi_dns_packet_free(p);
672         return;
673     }
674
675     n = 1;
676     
677     /* Try to fill up packet with more probes, if available */
678     for (pj = s->probe_jobs; pj; pj = pj->jobs_next) {
679
680         if (pj->chosen)
681             continue;
682         
683         if (!packet_add_probe_query(s, p, pj))
684             break;
685         
686         n++;
687     }
688
689     avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_QDCOUNT, n);
690
691     n = 0;
692
693     /* Now add the chosen records to the authorative section */
694     for (pj = s->probe_jobs; pj; pj = next) {
695
696         next = pj->jobs_next;
697
698         if (!pj->chosen)
699             continue;
700
701         if (!avahi_dns_packet_append_record(p, pj->record, TRUE)) {
702             g_warning("Bad probe size estimate!");
703
704             /* Unmark all following jobs */
705             for (; pj; pj = pj->jobs_next)
706                 pj->chosen = FALSE;
707             
708             break;
709         }
710
711         probe_job_free(s, pj);
712         
713         n ++;
714     }
715     
716     avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_NSCOUNT, n);
717
718     /* Send it now */
719     avahi_interface_send_packet(s->interface, p);
720     avahi_dns_packet_free(p);
721 }
722
723 void avahi_packet_scheduler_post_probe(AvahiPacketScheduler *s, AvahiRecord *record, gboolean immediately) {
724     AvahiProbeJob *pj;
725     GTimeVal tv;
726     
727     g_assert(s);
728     g_assert(record);
729     g_assert(!avahi_key_is_pattern(record->key));
730     
731     avahi_elapse_time(&tv, immediately ? 0 : AVAHI_PROBE_DEFER_MSEC, 0);
732
733     /* Create a new job and schedule it */
734     pj = probe_job_new(s, record);
735     pj->delivery = tv;
736     pj->time_event = avahi_time_event_queue_add(s->server->time_event_queue, &pj->delivery, probe_elapse, pj);
737 }