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