2 This file is part of catta.
4 catta is free software; you can redistribute it and/or modify it
5 under the terms of the GNU Lesser General Public License as
6 published by the Free Software Foundation; either version 2.1 of the
7 License, or (at your option) any later version.
9 catta is distributed in the hope that it will be useful, but WITHOUT
10 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
11 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
12 Public License for more details.
14 You should have received a copy of the GNU Lesser General Public
15 License along with catta; if not, write to the Free Software
16 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
26 #include <catta/timeval.h>
27 #include <catta/malloc.h>
29 #include "query-sched.h"
30 #include <catta/log.h>
32 #define CATTA_QUERY_HISTORY_MSEC 100
33 #define CATTA_QUERY_DEFER_MSEC 100
35 typedef struct CattaQueryJob CattaQueryJob;
36 typedef struct CattaKnownAnswer CattaKnownAnswer;
38 struct CattaQueryJob {
42 CattaQueryScheduler *scheduler;
43 CattaTimeEvent *time_event;
46 struct timeval delivery;
50 /* Jobs are stored in a simple linked list. It might turn out in
51 * the future that this list grows too long and we must switch to
52 * some other kind of data structure. This needs further
53 * investigation. I expect the list to be very short (< 20
54 * entries) most of the time, but this might be a wrong
55 * assumption, especially on setups where traffic reflection is
58 CATTA_LLIST_FIELDS(CattaQueryJob, jobs);
61 struct CattaKnownAnswer {
62 CattaQueryScheduler *scheduler;
65 CATTA_LLIST_FIELDS(CattaKnownAnswer, known_answer);
68 struct CattaQueryScheduler {
69 CattaInterface *iface;
70 CattaTimeEventQueue *time_event_queue;
74 CATTA_LLIST_HEAD(CattaQueryJob, jobs);
75 CATTA_LLIST_HEAD(CattaQueryJob, history);
76 CATTA_LLIST_HEAD(CattaKnownAnswer, known_answers);
79 static CattaQueryJob* job_new(CattaQueryScheduler *s, CattaKey *key, int done) {
85 if (!(qj = catta_new(CattaQueryJob, 1))) {
86 catta_log_error(__FILE__": Out of memory");
91 qj->key = catta_key_ref(key);
92 qj->time_event = NULL;
94 qj->id = s->next_id++;
96 if ((qj->done = done))
97 CATTA_LLIST_PREPEND(CattaQueryJob, jobs, s->history, qj);
99 CATTA_LLIST_PREPEND(CattaQueryJob, jobs, s->jobs, qj);
104 static void job_free(CattaQueryScheduler *s, CattaQueryJob *qj) {
109 catta_time_event_free(qj->time_event);
112 CATTA_LLIST_REMOVE(CattaQueryJob, jobs, s->history, qj);
114 CATTA_LLIST_REMOVE(CattaQueryJob, jobs, s->jobs, qj);
116 catta_key_unref(qj->key);
120 static void elapse_callback(CattaTimeEvent *e, void* data);
122 static void job_set_elapse_time(CattaQueryScheduler *s, CattaQueryJob *qj, unsigned msec, unsigned jitter) {
128 catta_elapse_time(&tv, msec, jitter);
131 catta_time_event_update(qj->time_event, &tv);
133 qj->time_event = catta_time_event_new(s->time_event_queue, &tv, elapse_callback, qj);
136 static void job_mark_done(CattaQueryScheduler *s, CattaQueryJob *qj) {
142 CATTA_LLIST_REMOVE(CattaQueryJob, jobs, s->jobs, qj);
143 CATTA_LLIST_PREPEND(CattaQueryJob, jobs, s->history, qj);
147 job_set_elapse_time(s, qj, CATTA_QUERY_HISTORY_MSEC, 0);
148 gettimeofday(&qj->delivery, NULL);
151 CattaQueryScheduler *catta_query_scheduler_new(CattaInterface *i) {
152 CattaQueryScheduler *s;
155 if (!(s = catta_new(CattaQueryScheduler, 1))) {
156 catta_log_error(__FILE__": Out of memory");
157 return NULL; /* OOM */
161 s->time_event_queue = i->monitor->server->time_event_queue;
164 CATTA_LLIST_HEAD_INIT(CattaQueryJob, s->jobs);
165 CATTA_LLIST_HEAD_INIT(CattaQueryJob, s->history);
166 CATTA_LLIST_HEAD_INIT(CattaKnownAnswer, s->known_answers);
171 void catta_query_scheduler_free(CattaQueryScheduler *s) {
174 assert(!s->known_answers);
175 catta_query_scheduler_clear(s);
179 void catta_query_scheduler_clear(CattaQueryScheduler *s) {
183 job_free(s, s->jobs);
185 job_free(s, s->history);
188 static void* known_answer_walk_callback(CattaCache *c, CattaKey *pattern, CattaCacheEntry *e, void* userdata) {
189 CattaQueryScheduler *s = userdata;
190 CattaKnownAnswer *ka;
197 if (catta_cache_entry_half_ttl(c, e))
200 if (!(ka = catta_new0(CattaKnownAnswer, 1))) {
201 catta_log_error(__FILE__": Out of memory");
206 ka->record = catta_record_ref(e->record);
208 CATTA_LLIST_PREPEND(CattaKnownAnswer, known_answer, s->known_answers, ka);
212 static int packet_add_query_job(CattaQueryScheduler *s, CattaDnsPacket *p, CattaQueryJob *qj) {
217 if (!catta_dns_packet_append_key(p, qj->key, 0))
220 /* Add all matching known answers to the list */
221 catta_cache_walk(s->iface->cache, qj->key, known_answer_walk_callback, s);
223 job_mark_done(s, qj);
228 static void append_known_answers_and_send(CattaQueryScheduler *s, CattaDnsPacket *p) {
229 CattaKnownAnswer *ka;
236 while ((ka = s->known_answers)) {
239 while (!catta_dns_packet_append_record(p, ka->record, 0, 0)) {
241 if (catta_dns_packet_is_empty(p)) {
242 /* The record is too large to fit into one packet, so
243 there's no point in sending it. Better is letting
244 the owner of the record send it as a response. This
245 has the advantage of a cache refresh. */
251 catta_dns_packet_set_field(p, CATTA_DNS_FIELD_FLAGS, catta_dns_packet_get_field(p, CATTA_DNS_FIELD_FLAGS) | CATTA_DNS_FLAG_TC);
252 catta_dns_packet_set_field(p, CATTA_DNS_FIELD_ANCOUNT, n);
253 catta_interface_send_packet(s->iface, p);
254 catta_dns_packet_free(p);
256 p = catta_dns_packet_new_query(s->iface->hardware->mtu);
260 CATTA_LLIST_REMOVE(CattaKnownAnswer, known_answer, s->known_answers, ka);
261 catta_record_unref(ka->record);
268 catta_dns_packet_set_field(p, CATTA_DNS_FIELD_ANCOUNT, n);
269 catta_interface_send_packet(s->iface, p);
270 catta_dns_packet_free(p);
273 static void elapse_callback(CATTA_GCC_UNUSED CattaTimeEvent *e, void* data) {
274 CattaQueryJob *qj = data;
275 CattaQueryScheduler *s;
284 /* Lets remove it from the history */
289 assert(!s->known_answers);
291 if (!(p = catta_dns_packet_new_query(s->iface->hardware->mtu)))
294 b = packet_add_query_job(s, p, qj);
295 assert(b); /* An query must always fit in */
298 /* Try to fill up packet with more queries, if available */
301 if (!packet_add_query_job(s, p, s->jobs))
307 catta_dns_packet_set_field(p, CATTA_DNS_FIELD_QDCOUNT, n);
309 /* Now add known answers */
310 append_known_answers_and_send(s, p);
313 static CattaQueryJob* find_scheduled_job(CattaQueryScheduler *s, CattaKey *key) {
319 for (qj = s->jobs; qj; qj = qj->jobs_next) {
322 if (catta_key_equal(qj->key, key))
329 static CattaQueryJob* find_history_job(CattaQueryScheduler *s, CattaKey *key) {
335 for (qj = s->history; qj; qj = qj->jobs_next) {
338 if (catta_key_equal(qj->key, key)) {
339 /* Check whether this entry is outdated */
341 if (catta_age(&qj->delivery) > CATTA_QUERY_HISTORY_MSEC*1000) {
342 /* it is outdated, so let's remove it */
354 int catta_query_scheduler_post(CattaQueryScheduler *s, CattaKey *key, int immediately, unsigned *ret_id) {
361 if ((qj = find_history_job(s, key)))
364 catta_elapse_time(&tv, immediately ? 0 : CATTA_QUERY_DEFER_MSEC, 0);
366 if ((qj = find_scheduled_job(s, key))) {
367 /* Duplicate questions suppression */
369 if (catta_timeval_compare(&tv, &qj->delivery) < 0) {
370 /* If the new entry should be scheduled earlier,
371 * update the old entry */
373 catta_time_event_update(qj->time_event, &qj->delivery);
380 if (!(qj = job_new(s, key, 0)))
384 qj->time_event = catta_time_event_new(s->time_event_queue, &qj->delivery, elapse_callback, qj);
393 void catta_query_scheduler_incoming(CattaQueryScheduler *s, CattaKey *key) {
399 /* This function is called whenever an incoming query was
400 * received. We drop scheduled queries that match. The keyword is
401 * "DUPLICATE QUESTION SUPPRESION". */
403 if ((qj = find_scheduled_job(s, key))) {
404 job_mark_done(s, qj);
408 /* Look if there's a history job for this key. If there is, just
409 * update the elapse time */
410 if (!(qj = find_history_job(s, key)))
411 if (!(qj = job_new(s, key, 1)))
414 gettimeofday(&qj->delivery, NULL);
415 job_set_elapse_time(s, qj, CATTA_QUERY_HISTORY_MSEC, 0);
418 int catta_query_scheduler_withdraw_by_id(CattaQueryScheduler *s, unsigned id) {
423 /* Very short lived queries can withdraw an already scheduled item
424 * from the queue using this function, simply by passing the id
425 * returned by catta_query_scheduler_post(). */
427 for (qj = s->jobs; qj; qj = qj->jobs_next) {
433 assert(qj->n_posted >= 1);
435 if (--qj->n_posted <= 0) {
437 /* We withdraw this job only if the calling object was
438 * the only remaining poster. (Usually this is the
439 * case since there should exist only one querier per
440 * key, but there are exceptions, notably reflected