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 <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
  37 typedef struct AvahiQueryJob AvahiQueryJob;
  38 typedef struct AvahiKnownAnswer AvahiKnownAnswer;
  39
  40 struct 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
  63 struct AvahiKnownAnswer {
  64     AvahiQueryScheduler *scheduler;
  65     AvahiRecord *record;
  66
  67     AVAHI_LLIST_FIELDS(AvahiKnownAnswer, known_answer);
  68 };
  69
  70 struct 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
  81 static 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
 106 static 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
 122 static void elapse_callback(AvahiTimeEvent *e, void* data);
 123
 124 static 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
 138 static 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
 153 AvahiQueryScheduler *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
 173 void 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
 181 void 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
 190 static 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
 214 static 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
 230 static 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
 275 static 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
 315 static 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
 331 static 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
 356 int 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
 395 void 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
 420 int 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 }