4 This file is part of avahi.
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.
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.
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
28 #include <avahi-common/timeval.h>
29 #include <avahi-common/malloc.h>
31 #include "query-sched.h"
34 #define AVAHI_QUERY_HISTORY_MSEC 100
35 #define AVAHI_QUERY_DEFER_MSEC 100
37 typedef struct AvahiQueryJob AvahiQueryJob;
38 typedef struct AvahiKnownAnswer AvahiKnownAnswer;
40 struct AvahiQueryJob {
44 AvahiQueryScheduler *scheduler;
45 AvahiTimeEvent *time_event;
48 struct timeval delivery;
52 /* Jobs are stored in a simple linked list. It might turn out in
53 * the future that this list grows too long and we must switch to
54 * some other kind of data structure. This needs further
55 * investigation. I expect the list to be very short (< 20
56 * entries) most of the time, but this might be a wrong
57 * assumption, especially on setups where traffic reflection is
60 AVAHI_LLIST_FIELDS(AvahiQueryJob, jobs);
63 struct AvahiKnownAnswer {
64 AvahiQueryScheduler *scheduler;
67 AVAHI_LLIST_FIELDS(AvahiKnownAnswer, known_answer);
70 struct AvahiQueryScheduler {
71 AvahiInterface *interface;
72 AvahiTimeEventQueue *time_event_queue;
76 AVAHI_LLIST_HEAD(AvahiQueryJob, jobs);
77 AVAHI_LLIST_HEAD(AvahiQueryJob, history);
78 AVAHI_LLIST_HEAD(AvahiKnownAnswer, known_answers);
81 static AvahiQueryJob* job_new(AvahiQueryScheduler *s, AvahiKey *key, int done) {
87 if (!(qj = avahi_new(AvahiQueryJob, 1))) {
88 avahi_log_error(__FILE__": Out of memory");
93 qj->key = avahi_key_ref(key);
94 qj->time_event = NULL;
96 qj->id = s->next_id++;
98 if ((qj->done = done))
99 AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->history, qj);
101 AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->jobs, qj);
106 static void job_free(AvahiQueryScheduler *s, AvahiQueryJob *qj) {
111 avahi_time_event_free(qj->time_event);
114 AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->history, qj);
116 AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->jobs, qj);
118 avahi_key_unref(qj->key);
122 static void elapse_callback(AvahiTimeEvent *e, void* data);
124 static void job_set_elapse_time(AvahiQueryScheduler *s, AvahiQueryJob *qj, unsigned msec, unsigned jitter) {
130 avahi_elapse_time(&tv, msec, jitter);
133 avahi_time_event_update(qj->time_event, &tv);
135 qj->time_event = avahi_time_event_new(s->time_event_queue, &tv, elapse_callback, qj);
138 static void job_mark_done(AvahiQueryScheduler *s, AvahiQueryJob *qj) {
144 AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->jobs, qj);
145 AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->history, qj);
149 job_set_elapse_time(s, qj, AVAHI_QUERY_HISTORY_MSEC, 0);
150 gettimeofday(&qj->delivery, NULL);
153 AvahiQueryScheduler *avahi_query_scheduler_new(AvahiInterface *i) {
154 AvahiQueryScheduler *s;
157 if (!(s = avahi_new(AvahiQueryScheduler, 1))) {
158 avahi_log_error(__FILE__": Out of memory");
159 return NULL; /* OOM */
163 s->time_event_queue = i->monitor->server->time_event_queue;
166 AVAHI_LLIST_HEAD_INIT(AvahiQueryJob, s->jobs);
167 AVAHI_LLIST_HEAD_INIT(AvahiQueryJob, s->history);
168 AVAHI_LLIST_HEAD_INIT(AvahiKnownAnswer, s->known_answers);
173 void avahi_query_scheduler_free(AvahiQueryScheduler *s) {
176 assert(!s->known_answers);
177 avahi_query_scheduler_clear(s);
181 void avahi_query_scheduler_clear(AvahiQueryScheduler *s) {
185 job_free(s, s->jobs);
187 job_free(s, s->history);
190 static void* known_answer_walk_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void* userdata) {
191 AvahiQueryScheduler *s = userdata;
192 AvahiKnownAnswer *ka;
199 if (avahi_cache_entry_half_ttl(c, e))
202 if (!(ka = avahi_new0(AvahiKnownAnswer, 1))) {
203 avahi_log_error(__FILE__": Out of memory");
208 ka->record = avahi_record_ref(e->record);
210 AVAHI_LLIST_PREPEND(AvahiKnownAnswer, known_answer, s->known_answers, ka);
214 static int packet_add_query_job(AvahiQueryScheduler *s, AvahiDnsPacket *p, AvahiQueryJob *qj) {
219 if (!avahi_dns_packet_append_key(p, qj->key, 0))
222 /* Add all matching known answers to the list */
223 avahi_cache_walk(s->interface->cache, qj->key, known_answer_walk_callback, s);
225 job_mark_done(s, qj);
230 static void append_known_answers_and_send(AvahiQueryScheduler *s, AvahiDnsPacket *p) {
231 AvahiKnownAnswer *ka;
238 while ((ka = s->known_answers)) {
241 while (!avahi_dns_packet_append_record(p, ka->record, 0, 0)) {
243 if (avahi_dns_packet_is_empty(p)) {
244 /* The record is too large to fit into one packet, so
245 there's no point in sending it. Better is letting
246 the owner of the record send it as a response. This
247 has the advantage of a cache refresh. */
253 avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_FLAGS, avahi_dns_packet_get_field(p, AVAHI_DNS_FIELD_FLAGS) | AVAHI_DNS_FLAG_TC);
254 avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_ANCOUNT, n);
255 avahi_interface_send_packet(s->interface, p);
256 avahi_dns_packet_free(p);
258 p = avahi_dns_packet_new_query(s->interface->hardware->mtu);
262 AVAHI_LLIST_REMOVE(AvahiKnownAnswer, known_answer, s->known_answers, ka);
263 avahi_record_unref(ka->record);
270 avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_ANCOUNT, n);
271 avahi_interface_send_packet(s->interface, p);
272 avahi_dns_packet_free(p);
275 static void elapse_callback(AVAHI_GCC_UNUSED AvahiTimeEvent *e, void* data) {
276 AvahiQueryJob *qj = data;
277 AvahiQueryScheduler *s;
286 /* Lets remove it from the history */
291 assert(!s->known_answers);
293 if (!(p = avahi_dns_packet_new_query(s->interface->hardware->mtu)))
296 b = packet_add_query_job(s, p, qj);
297 assert(b); /* An query must always fit in */
300 /* Try to fill up packet with more queries, if available */
303 if (!packet_add_query_job(s, p, s->jobs))
309 avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_QDCOUNT, n);
311 /* Now add known answers */
312 append_known_answers_and_send(s, p);
315 static AvahiQueryJob* find_scheduled_job(AvahiQueryScheduler *s, AvahiKey *key) {
321 for (qj = s->jobs; qj; qj = qj->jobs_next) {
324 if (avahi_key_equal(qj->key, key))
331 static AvahiQueryJob* find_history_job(AvahiQueryScheduler *s, AvahiKey *key) {
337 for (qj = s->history; qj; qj = qj->jobs_next) {
340 if (avahi_key_equal(qj->key, key)) {
341 /* Check whether this entry is outdated */
343 if (avahi_age(&qj->delivery) > AVAHI_QUERY_HISTORY_MSEC*1000) {
344 /* it is outdated, so let's remove it */
356 int avahi_query_scheduler_post(AvahiQueryScheduler *s, AvahiKey *key, int immediately, unsigned *ret_id) {
363 if ((qj = find_history_job(s, key)))
366 avahi_elapse_time(&tv, immediately ? 0 : AVAHI_QUERY_DEFER_MSEC, 0);
368 if ((qj = find_scheduled_job(s, key))) {
369 /* Duplicate questions suppression */
371 if (avahi_timeval_compare(&tv, &qj->delivery) < 0) {
372 /* If the new entry should be scheduled earlier,
373 * update the old entry */
375 avahi_time_event_update(qj->time_event, &qj->delivery);
382 if (!(qj = job_new(s, key, 0)))
386 qj->time_event = avahi_time_event_new(s->time_event_queue, &qj->delivery, elapse_callback, qj);
395 void avahi_query_scheduler_incoming(AvahiQueryScheduler *s, AvahiKey *key) {
401 /* This function is called whenever an incoming query was
402 * received. We drop scheduled queries that match. The keyword is
403 * "DUPLICATE QUESTION SUPPRESION". */
405 if ((qj = find_scheduled_job(s, key))) {
406 job_mark_done(s, qj);
410 /* Look if there's a history job for this key. If there is, just
411 * update the elapse time */
412 if (!(qj = find_history_job(s, key)))
413 if (!(qj = job_new(s, key, 1)))
416 gettimeofday(&qj->delivery, NULL);
417 job_set_elapse_time(s, qj, AVAHI_QUERY_HISTORY_MSEC, 0);
420 int avahi_query_scheduler_withdraw_by_id(AvahiQueryScheduler *s, unsigned id) {
425 /* Very short lived queries can withdraw an already scheduled item
426 * from the queue using this function, simply by passing the id
427 * returned by avahi_query_scheduler_post(). */
429 for (qj = s->jobs; qj; qj = qj->jobs_next) {
435 assert(qj->n_posted >= 1);
437 if (--qj->n_posted <= 0) {
439 /* We withdraw this job only if the calling object was
440 * the only remaining poster. (Usually this is the
441 * case since there should exist only one querier per
442 * key, but there are exceptions, notably reflected