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 <stdlib.h>
27
28#include <avahi-common/timeval.h>
29#include <avahi-common/malloc.h>
30
31#include "query-sched.h"
32#include "log.h"
33
34#define AVAHI_QUERY_HISTORY_MSEC 100
35#define AVAHI_QUERY_DEFER_MSEC 100
36
37typedef struct AvahiQueryJob AvahiQueryJob;
38typedef struct AvahiKnownAnswer AvahiKnownAnswer;
39
40struct AvahiQueryJob {
41    unsigned id;
42    int n_posted;
43
44    AvahiQueryScheduler *scheduler;
45    AvahiTimeEvent *time_event;
46
47    int done;
48    struct timeval delivery;
49
50    AvahiKey *key;
51
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
58     * involved. */
59
60    AVAHI_LLIST_FIELDS(AvahiQueryJob, jobs);
61};
62
63struct AvahiKnownAnswer {
64    AvahiQueryScheduler *scheduler;
65    AvahiRecord *record;
66
67    AVAHI_LLIST_FIELDS(AvahiKnownAnswer, known_answer);
68};
69
70struct AvahiQueryScheduler {
71    AvahiInterface *interface;
72    AvahiTimeEventQueue *time_event_queue;
73
74    unsigned next_id;
75
76    AVAHI_LLIST_HEAD(AvahiQueryJob, jobs);
77    AVAHI_LLIST_HEAD(AvahiQueryJob, history);
78    AVAHI_LLIST_HEAD(AvahiKnownAnswer, known_answers);
79};
80
81static AvahiQueryJob* job_new(AvahiQueryScheduler *s, AvahiKey *key, int done) {
82    AvahiQueryJob *qj;
83
84    assert(s);
85    assert(key);
86
87    if (!(qj = avahi_new(AvahiQueryJob, 1))) {
88        avahi_log_error(__FILE__": Out of memory");
89        return NULL;
90    }
91
92    qj->scheduler = s;
93    qj->key = avahi_key_ref(key);
94    qj->time_event = NULL;
95    qj->n_posted = 1;
96    qj->id = s->next_id++;
97
98    if ((qj->done = done))
99        AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->history, qj);
100    else
101        AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->jobs, qj);
102
103    return qj;
104}
105
106static void job_free(AvahiQueryScheduler *s, AvahiQueryJob *qj) {
107    assert(s);
108    assert(qj);
109
110    if (qj->time_event)
111        avahi_time_event_free(qj->time_event);
112
113    if (qj->done)
114        AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->history, qj);
115    else
116        AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->jobs, qj);
117
118    avahi_key_unref(qj->key);
119    avahi_free(qj);
120}
121
122static void elapse_callback(AvahiTimeEvent *e, void* data);
123
124static void job_set_elapse_time(AvahiQueryScheduler *s, AvahiQueryJob *qj, unsigned msec, unsigned jitter) {
125    struct timeval tv;
126
127    assert(s);
128    assert(qj);
129
130    avahi_elapse_time(&tv, msec, jitter);
131
132    if (qj->time_event)
133        avahi_time_event_update(qj->time_event, &tv);
134    else
135        qj->time_event = avahi_time_event_new(s->time_event_queue, &tv, elapse_callback, qj);
136}
137
138static void job_mark_done(AvahiQueryScheduler *s, AvahiQueryJob *qj) {
139    assert(s);
140    assert(qj);
141
142    assert(!qj->done);
143
144    AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->jobs, qj);
145    AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->history, qj);
146
147    qj->done = 1;
148
149    job_set_elapse_time(s, qj, AVAHI_QUERY_HISTORY_MSEC, 0);
150    gettimeofday(&qj->delivery, NULL);
151}
152
153AvahiQueryScheduler *avahi_query_scheduler_new(AvahiInterface *i) {
154    AvahiQueryScheduler *s;
155    assert(i);
156
157    if (!(s = avahi_new(AvahiQueryScheduler, 1))) {
158        avahi_log_error(__FILE__": Out of memory");
159        return NULL; /* OOM */
160    }
161
162    s->interface = i;
163    s->time_event_queue = i->monitor->server->time_event_queue;
164    s->next_id = 0;
165
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);
169
170    return s;
171}
172
173void avahi_query_scheduler_free(AvahiQueryScheduler *s) {
174    assert(s);
175
176    assert(!s->known_answers);
177    avahi_query_scheduler_clear(s);
178    avahi_free(s);
179}
180
181void avahi_query_scheduler_clear(AvahiQueryScheduler *s) {
182    assert(s);
183
184    while (s->jobs)
185        job_free(s, s->jobs);
186    while (s->history)
187        job_free(s, s->history);
188}
189
190static void* known_answer_walk_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void* userdata) {
191    AvahiQueryScheduler *s = userdata;
192    AvahiKnownAnswer *ka;
193
194    assert(c);
195    assert(pattern);
196    assert(e);
197    assert(s);
198
199    if (avahi_cache_entry_half_ttl(c, e))
200        return NULL;
201
202    if (!(ka = avahi_new0(AvahiKnownAnswer, 1))) {
203        avahi_log_error(__FILE__": Out of memory");
204        return NULL;
205    }
206
207    ka->scheduler = s;
208    ka->record = avahi_record_ref(e->record);
209
210    AVAHI_LLIST_PREPEND(AvahiKnownAnswer, known_answer, s->known_answers, ka);
211    return NULL;
212}
213
214static int packet_add_query_job(AvahiQueryScheduler *s, AvahiDnsPacket *p, AvahiQueryJob *qj) {
215    assert(s);
216    assert(p);
217    assert(qj);
218
219    if (!avahi_dns_packet_append_key(p, qj->key, 0))
220        return 0;
221
222    /* Add all matching known answers to the list */
223    avahi_cache_walk(s->interface->cache, qj->key, known_answer_walk_callback, s);
224
225    job_mark_done(s, qj);
226
227    return 1;
228}
229
230static void append_known_answers_and_send(AvahiQueryScheduler *s, AvahiDnsPacket *p) {
231    AvahiKnownAnswer *ka;
232    unsigned n;
233    assert(s);
234    assert(p);
235
236    n = 0;
237
238    while ((ka = s->known_answers)) {
239        int too_large = 0;
240
241        while (!avahi_dns_packet_append_record(p, ka->record, 0, 0)) {
242
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. */
248
249                too_large = 1;
250                break;
251            }
252
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);
257
258            p = avahi_dns_packet_new_query(s->interface->hardware->mtu);
259            n = 0;
260        }
261
262        AVAHI_LLIST_REMOVE(AvahiKnownAnswer, known_answer, s->known_answers, ka);
263        avahi_record_unref(ka->record);
264        avahi_free(ka);
265
266        if (!too_large)
267            n++;
268    }
269
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);
273}
274
275static void elapse_callback(AVAHI_GCC_UNUSED AvahiTimeEvent *e, void* data) {
276    AvahiQueryJob *qj = data;
277    AvahiQueryScheduler *s;
278    AvahiDnsPacket *p;
279    unsigned n;
280    int b;
281
282    assert(qj);
283    s = qj->scheduler;
284
285    if (qj->done) {
286        /* Lets remove it  from the history */
287        job_free(s, qj);
288        return;
289    }
290
291    assert(!s->known_answers);
292
293    if (!(p = avahi_dns_packet_new_query(s->interface->hardware->mtu)))
294        return; /* OOM */
295
296    b = packet_add_query_job(s, p, qj);
297    assert(b); /* An query must always fit in */
298    n = 1;
299
300    /* Try to fill up packet with more queries, if available */
301    while (s->jobs) {
302
303        if (!packet_add_query_job(s, p, s->jobs))
304            break;
305
306        n++;
307    }
308
309    avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_QDCOUNT, n);
310
311    /* Now add known answers */
312    append_known_answers_and_send(s, p);
313}
314
315static AvahiQueryJob* find_scheduled_job(AvahiQueryScheduler *s, AvahiKey *key) {
316    AvahiQueryJob *qj;
317
318    assert(s);
319    assert(key);
320
321    for (qj = s->jobs; qj; qj = qj->jobs_next) {
322        assert(!qj->done);
323
324        if (avahi_key_equal(qj->key, key))
325            return qj;
326    }
327
328    return NULL;
329}
330
331static AvahiQueryJob* find_history_job(AvahiQueryScheduler *s, AvahiKey *key) {
332    AvahiQueryJob *qj;
333
334    assert(s);
335    assert(key);
336
337    for (qj = s->history; qj; qj = qj->jobs_next) {
338        assert(qj->done);
339
340        if (avahi_key_equal(qj->key, key)) {
341            /* Check whether this entry is outdated */
342
343            if (avahi_age(&qj->delivery) > AVAHI_QUERY_HISTORY_MSEC*1000) {
344                /* it is outdated, so let's remove it */
345                job_free(s, qj);
346                return NULL;
347            }
348
349            return qj;
350        }
351    }
352
353    return NULL;
354}
355
356int avahi_query_scheduler_post(AvahiQueryScheduler *s, AvahiKey *key, int immediately, unsigned *ret_id) {
357    struct timeval tv;
358    AvahiQueryJob *qj;
359
360    assert(s);
361    assert(key);
362
363    if ((qj = find_history_job(s, key)))
364        return 0;
365
366    avahi_elapse_time(&tv, immediately ? 0 : AVAHI_QUERY_DEFER_MSEC, 0);
367
368    if ((qj = find_scheduled_job(s, key))) {
369        /* Duplicate questions suppression */
370
371        if (avahi_timeval_compare(&tv, &qj->delivery) < 0) {
372            /* If the new entry should be scheduled earlier,
373             * update the old entry */
374            qj->delivery = tv;
375            avahi_time_event_update(qj->time_event, &qj->delivery);
376        }
377
378        qj->n_posted++;
379
380    } else {
381
382        if (!(qj = job_new(s, key, 0)))
383            return 0; /* OOM */
384
385        qj->delivery = tv;
386        qj->time_event = avahi_time_event_new(s->time_event_queue, &qj->delivery, elapse_callback, qj);
387    }
388
389    if (ret_id)
390        *ret_id = qj->id;
391
392    return 1;
393}
394
395void avahi_query_scheduler_incoming(AvahiQueryScheduler *s, AvahiKey *key) {
396    AvahiQueryJob *qj;
397
398    assert(s);
399    assert(key);
400
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". */
404
405    if ((qj = find_scheduled_job(s, key))) {
406        job_mark_done(s, qj);
407        return;
408    }
409
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)))
414            return; /* OOM */
415
416    gettimeofday(&qj->delivery, NULL);
417    job_set_elapse_time(s, qj, AVAHI_QUERY_HISTORY_MSEC, 0);
418}
419
420int avahi_query_scheduler_withdraw_by_id(AvahiQueryScheduler *s, unsigned id) {
421    AvahiQueryJob *qj;
422
423    assert(s);
424
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(). */
428
429    for (qj = s->jobs; qj; qj = qj->jobs_next) {
430        assert(!qj->done);
431
432        if (qj->id == id) {
433            /* Entry found */
434
435            assert(qj->n_posted >= 1);
436
437            if (--qj->n_posted <= 0) {
438
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
443                 * traffic.) */
444
445                job_free(s, qj);
446                return 1;
447            }
448        }
449    }
450
451    return 0;
452}
453