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