+++ /dev/null
-/***
- This file is part of avahi.
-
- avahi is free software; you can redistribute it and/or modify it
- under the terms of the GNU Lesser General Public License as
- published by the Free Software Foundation; either version 2.1 of the
- License, or (at your option) any later version.
-
- avahi is distributed in the hope that it will be useful, but WITHOUT
- ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
- or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
- Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public
- License along with avahi; if not, write to the Free Software
- Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
- USA.
-***/
-
-#ifdef HAVE_CONFIG_H
-#include <config.h>
-#endif
-
-#include <stdlib.h>
-
-#include <avahi-common/timeval.h>
-#include <avahi-common/malloc.h>
-
-#include "query-sched.h"
-#include "log.h"
-
-#define AVAHI_QUERY_HISTORY_MSEC 100
-#define AVAHI_QUERY_DEFER_MSEC 100
-
-typedef struct AvahiQueryJob AvahiQueryJob;
-typedef struct AvahiKnownAnswer AvahiKnownAnswer;
-
-struct AvahiQueryJob {
- unsigned id;
- int n_posted;
-
- AvahiQueryScheduler *scheduler;
- AvahiTimeEvent *time_event;
-
- int done;
- struct timeval delivery;
-
- AvahiKey *key;
-
- /* Jobs are stored in a simple linked list. It might turn out in
- * the future that this list grows too long and we must switch to
- * some other kind of data structure. This needs further
- * investigation. I expect the list to be very short (< 20
- * entries) most of the time, but this might be a wrong
- * assumption, especially on setups where traffic reflection is
- * involved. */
-
- AVAHI_LLIST_FIELDS(AvahiQueryJob, jobs);
-};
-
-struct AvahiKnownAnswer {
- AvahiQueryScheduler *scheduler;
- AvahiRecord *record;
-
- AVAHI_LLIST_FIELDS(AvahiKnownAnswer, known_answer);
-};
-
-struct AvahiQueryScheduler {
- AvahiInterface *interface;
- AvahiTimeEventQueue *time_event_queue;
-
- unsigned next_id;
-
- AVAHI_LLIST_HEAD(AvahiQueryJob, jobs);
- AVAHI_LLIST_HEAD(AvahiQueryJob, history);
- AVAHI_LLIST_HEAD(AvahiKnownAnswer, known_answers);
-};
-
-static AvahiQueryJob* job_new(AvahiQueryScheduler *s, AvahiKey *key, int done) {
- AvahiQueryJob *qj;
-
- assert(s);
- assert(key);
-
- if (!(qj = avahi_new(AvahiQueryJob, 1))) {
- avahi_log_error(__FILE__": Out of memory");
- return NULL;
- }
-
- qj->scheduler = s;
- qj->key = avahi_key_ref(key);
- qj->time_event = NULL;
- qj->n_posted = 1;
- qj->id = s->next_id++;
-
- if ((qj->done = done))
- AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->history, qj);
- else
- AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->jobs, qj);
-
- return qj;
-}
-
-static void job_free(AvahiQueryScheduler *s, AvahiQueryJob *qj) {
- assert(s);
- assert(qj);
-
- if (qj->time_event)
- avahi_time_event_free(qj->time_event);
-
- if (qj->done)
- AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->history, qj);
- else
- AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->jobs, qj);
-
- avahi_key_unref(qj->key);
- avahi_free(qj);
-}
-
-static void elapse_callback(AvahiTimeEvent *e, void* data);
-
-static void job_set_elapse_time(AvahiQueryScheduler *s, AvahiQueryJob *qj, unsigned msec, unsigned jitter) {
- struct timeval tv;
-
- assert(s);
- assert(qj);
-
- avahi_elapse_time(&tv, msec, jitter);
-
- if (qj->time_event)
- avahi_time_event_update(qj->time_event, &tv);
- else
- qj->time_event = avahi_time_event_new(s->time_event_queue, &tv, elapse_callback, qj);
-}
-
-static void job_mark_done(AvahiQueryScheduler *s, AvahiQueryJob *qj) {
- assert(s);
- assert(qj);
-
- assert(!qj->done);
-
- AVAHI_LLIST_REMOVE(AvahiQueryJob, jobs, s->jobs, qj);
- AVAHI_LLIST_PREPEND(AvahiQueryJob, jobs, s->history, qj);
-
- qj->done = 1;
-
- job_set_elapse_time(s, qj, AVAHI_QUERY_HISTORY_MSEC, 0);
- gettimeofday(&qj->delivery, NULL);
-}
-
-AvahiQueryScheduler *avahi_query_scheduler_new(AvahiInterface *i) {
- AvahiQueryScheduler *s;
- assert(i);
-
- if (!(s = avahi_new(AvahiQueryScheduler, 1))) {
- avahi_log_error(__FILE__": Out of memory");
- return NULL; /* OOM */
- }
-
- s->interface = i;
- s->time_event_queue = i->monitor->server->time_event_queue;
- s->next_id = 0;
-
- AVAHI_LLIST_HEAD_INIT(AvahiQueryJob, s->jobs);
- AVAHI_LLIST_HEAD_INIT(AvahiQueryJob, s->history);
- AVAHI_LLIST_HEAD_INIT(AvahiKnownAnswer, s->known_answers);
-
- return s;
-}
-
-void avahi_query_scheduler_free(AvahiQueryScheduler *s) {
- assert(s);
-
- assert(!s->known_answers);
- avahi_query_scheduler_clear(s);
- avahi_free(s);
-}
-
-void avahi_query_scheduler_clear(AvahiQueryScheduler *s) {
- assert(s);
-
- while (s->jobs)
- job_free(s, s->jobs);
- while (s->history)
- job_free(s, s->history);
-}
-
-static void* known_answer_walk_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void* userdata) {
- AvahiQueryScheduler *s = userdata;
- AvahiKnownAnswer *ka;
-
- assert(c);
- assert(pattern);
- assert(e);
- assert(s);
-
- if (avahi_cache_entry_half_ttl(c, e))
- return NULL;
-
- if (!(ka = avahi_new0(AvahiKnownAnswer, 1))) {
- avahi_log_error(__FILE__": Out of memory");
- return NULL;
- }
-
- ka->scheduler = s;
- ka->record = avahi_record_ref(e->record);
-
- AVAHI_LLIST_PREPEND(AvahiKnownAnswer, known_answer, s->known_answers, ka);
- return NULL;
-}
-
-static int packet_add_query_job(AvahiQueryScheduler *s, AvahiDnsPacket *p, AvahiQueryJob *qj) {
- assert(s);
- assert(p);
- assert(qj);
-
- if (!avahi_dns_packet_append_key(p, qj->key, 0))
- return 0;
-
- /* Add all matching known answers to the list */
- avahi_cache_walk(s->interface->cache, qj->key, known_answer_walk_callback, s);
-
- job_mark_done(s, qj);
-
- return 1;
-}
-
-static void append_known_answers_and_send(AvahiQueryScheduler *s, AvahiDnsPacket *p) {
- AvahiKnownAnswer *ka;
- unsigned n;
- assert(s);
- assert(p);
-
- n = 0;
-
- while ((ka = s->known_answers)) {
- int too_large = 0;
-
- while (!avahi_dns_packet_append_record(p, ka->record, 0, 0)) {
-
- if (avahi_dns_packet_is_empty(p)) {
- /* The record is too large to fit into one packet, so
- there's no point in sending it. Better is letting
- the owner of the record send it as a response. This
- has the advantage of a cache refresh. */
-
- too_large = 1;
- break;
- }
-
- avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_FLAGS, avahi_dns_packet_get_field(p, AVAHI_DNS_FIELD_FLAGS) | AVAHI_DNS_FLAG_TC);
- avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_ANCOUNT, n);
- avahi_interface_send_packet(s->interface, p);
- avahi_dns_packet_free(p);
-
- p = avahi_dns_packet_new_query(s->interface->hardware->mtu);
- n = 0;
- }
-
- AVAHI_LLIST_REMOVE(AvahiKnownAnswer, known_answer, s->known_answers, ka);
- avahi_record_unref(ka->record);
- avahi_free(ka);
-
- if (!too_large)
- n++;
- }
-
- avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_ANCOUNT, n);
- avahi_interface_send_packet(s->interface, p);
- avahi_dns_packet_free(p);
-}
-
-static void elapse_callback(AVAHI_GCC_UNUSED AvahiTimeEvent *e, void* data) {
- AvahiQueryJob *qj = data;
- AvahiQueryScheduler *s;
- AvahiDnsPacket *p;
- unsigned n;
- int b;
-
- assert(qj);
- s = qj->scheduler;
-
- if (qj->done) {
- /* Lets remove it from the history */
- job_free(s, qj);
- return;
- }
-
- assert(!s->known_answers);
-
- if (!(p = avahi_dns_packet_new_query(s->interface->hardware->mtu)))
- return; /* OOM */
-
- b = packet_add_query_job(s, p, qj);
- assert(b); /* An query must always fit in */
- n = 1;
-
- /* Try to fill up packet with more queries, if available */
- while (s->jobs) {
-
- if (!packet_add_query_job(s, p, s->jobs))
- break;
-
- n++;
- }
-
- avahi_dns_packet_set_field(p, AVAHI_DNS_FIELD_QDCOUNT, n);
-
- /* Now add known answers */
- append_known_answers_and_send(s, p);
-}
-
-static AvahiQueryJob* find_scheduled_job(AvahiQueryScheduler *s, AvahiKey *key) {
- AvahiQueryJob *qj;
-
- assert(s);
- assert(key);
-
- for (qj = s->jobs; qj; qj = qj->jobs_next) {
- assert(!qj->done);
-
- if (avahi_key_equal(qj->key, key))
- return qj;
- }
-
- return NULL;
-}
-
-static AvahiQueryJob* find_history_job(AvahiQueryScheduler *s, AvahiKey *key) {
- AvahiQueryJob *qj;
-
- assert(s);
- assert(key);
-
- for (qj = s->history; qj; qj = qj->jobs_next) {
- assert(qj->done);
-
- if (avahi_key_equal(qj->key, key)) {
- /* Check whether this entry is outdated */
-
- if (avahi_age(&qj->delivery) > AVAHI_QUERY_HISTORY_MSEC*1000) {
- /* it is outdated, so let's remove it */
- job_free(s, qj);
- return NULL;
- }
-
- return qj;
- }
- }
-
- return NULL;
-}
-
-int avahi_query_scheduler_post(AvahiQueryScheduler *s, AvahiKey *key, int immediately, unsigned *ret_id) {
- struct timeval tv;
- AvahiQueryJob *qj;
-
- assert(s);
- assert(key);
-
- if ((qj = find_history_job(s, key)))
- return 0;
-
- avahi_elapse_time(&tv, immediately ? 0 : AVAHI_QUERY_DEFER_MSEC, 0);
-
- if ((qj = find_scheduled_job(s, key))) {
- /* Duplicate questions suppression */
-
- if (avahi_timeval_compare(&tv, &qj->delivery) < 0) {
- /* If the new entry should be scheduled earlier,
- * update the old entry */
- qj->delivery = tv;
- avahi_time_event_update(qj->time_event, &qj->delivery);
- }
-
- qj->n_posted++;
-
- } else {
-
- if (!(qj = job_new(s, key, 0)))
- return 0; /* OOM */
-
- qj->delivery = tv;
- qj->time_event = avahi_time_event_new(s->time_event_queue, &qj->delivery, elapse_callback, qj);
- }
-
- if (ret_id)
- *ret_id = qj->id;
-
- return 1;
-}
-
-void avahi_query_scheduler_incoming(AvahiQueryScheduler *s, AvahiKey *key) {
- AvahiQueryJob *qj;
-
- assert(s);
- assert(key);
-
- /* This function is called whenever an incoming query was
- * received. We drop scheduled queries that match. The keyword is
- * "DUPLICATE QUESTION SUPPRESION". */
-
- if ((qj = find_scheduled_job(s, key))) {
- job_mark_done(s, qj);
- return;
- }
-
- /* Look if there's a history job for this key. If there is, just
- * update the elapse time */
- if (!(qj = find_history_job(s, key)))
- if (!(qj = job_new(s, key, 1)))
- return; /* OOM */
-
- gettimeofday(&qj->delivery, NULL);
- job_set_elapse_time(s, qj, AVAHI_QUERY_HISTORY_MSEC, 0);
-}
-
-int avahi_query_scheduler_withdraw_by_id(AvahiQueryScheduler *s, unsigned id) {
- AvahiQueryJob *qj;
-
- assert(s);
-
- /* Very short lived queries can withdraw an already scheduled item
- * from the queue using this function, simply by passing the id
- * returned by avahi_query_scheduler_post(). */
-
- for (qj = s->jobs; qj; qj = qj->jobs_next) {
- assert(!qj->done);
-
- if (qj->id == id) {
- /* Entry found */
-
- assert(qj->n_posted >= 1);
-
- if (--qj->n_posted <= 0) {
-
- /* We withdraw this job only if the calling object was
- * the only remaining poster. (Usually this is the
- * case since there should exist only one querier per
- * key, but there are exceptions, notably reflected
- * traffic.) */
-
- job_free(s, qj);
- return 1;
- }
- }
- }
-
- return 0;
-}