QtZeroConf/avahi-core/query-sched.c

/***
  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;
}