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 <string.h> 27#include <stdlib.h> 28#include <time.h> 29 30#include <avahi-common/timeval.h> 31#include <avahi-common/malloc.h> 32 33#include "cache.h" 34#include "log.h" 35#include "rr-util.h" 36 37#define AVAHI_CACHE_ENTRIES_MAX 500 38 39static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) { 40 AvahiCacheEntry *t; 41 42 assert(c); 43 assert(e); 44 45/* avahi_log_debug("removing from cache: %p %p", c, e); */ 46 47 /* Remove from hash table */ 48 t = avahi_hashmap_lookup(c->hashmap, e->record->key); 49 AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e); 50 if (t) 51 avahi_hashmap_replace(c->hashmap, t->record->key, t); 52 else 53 avahi_hashmap_remove(c->hashmap, e->record->key); 54 55 /* Remove from linked list */ 56 AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e); 57 58 if (e->time_event) 59 avahi_time_event_free(e->time_event); 60 61 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE); 62 63 avahi_record_unref(e->record); 64 65 avahi_free(e); 66 67 assert(c->n_entries-- >= 1); 68} 69 70AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) { 71 AvahiCache *c; 72 assert(server); 73 74 if (!(c = avahi_new(AvahiCache, 1))) { 75 avahi_log_error(__FILE__": Out of memory."); 76 return NULL; /* OOM */ 77 } 78 79 c->server = server; 80 c->interface = iface; 81 82 if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) { 83 avahi_log_error(__FILE__": Out of memory."); 84 avahi_free(c); 85 return NULL; /* OOM */ 86 } 87 88 AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries); 89 c->n_entries = 0; 90 91 c->last_rand_timestamp = 0; 92 93 return c; 94} 95 96void avahi_cache_free(AvahiCache *c) { 97 assert(c); 98 99 while (c->entries) 100 remove_entry(c, c->entries); 101 assert(c->n_entries == 0); 102 103 avahi_hashmap_free(c->hashmap); 104 105 avahi_free(c); 106} 107 108static AvahiCacheEntry *lookup_key(AvahiCache *c, AvahiKey *k) { 109 assert(c); 110 assert(k); 111 112 assert(!avahi_key_is_pattern(k)); 113 114 return avahi_hashmap_lookup(c->hashmap, k); 115} 116 117void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) { 118 void* ret; 119 120 assert(c); 121 assert(pattern); 122 assert(cb); 123 124 if (avahi_key_is_pattern(pattern)) { 125 AvahiCacheEntry *e, *n; 126 127 for (e = c->entries; e; e = n) { 128 n = e->entry_next; 129 130 if (avahi_key_pattern_match(pattern, e->record->key)) 131 if ((ret = cb(c, pattern, e, userdata))) 132 return ret; 133 } 134 135 } else { 136 AvahiCacheEntry *e, *n; 137 138 for (e = lookup_key(c, pattern); e; e = n) { 139 n = e->by_key_next; 140 141 if ((ret = cb(c, pattern, e, userdata))) 142 return ret; 143 } 144 } 145 146 return NULL; 147} 148 149static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) { 150 assert(c); 151 assert(pattern); 152 assert(e); 153 154 if (avahi_record_equal_no_ttl(e->record, userdata)) 155 return e; 156 157 return NULL; 158} 159 160static AvahiCacheEntry *lookup_record(AvahiCache *c, AvahiRecord *r) { 161 assert(c); 162 assert(r); 163 164 return avahi_cache_walk(c, r->key, lookup_record_callback, r); 165} 166 167static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent); 168 169static void elapse_func(AvahiTimeEvent *t, void *userdata) { 170 AvahiCacheEntry *e = userdata; 171/* char *txt; */ 172 unsigned percent = 0; 173 174 assert(t); 175 assert(e); 176 177/* txt = avahi_record_to_string(e->record); */ 178 179 switch (e->state) { 180 181 case AVAHI_CACHE_EXPIRY_FINAL: 182 case AVAHI_CACHE_POOF_FINAL: 183 case AVAHI_CACHE_GOODBYE_FINAL: 184 case AVAHI_CACHE_REPLACE_FINAL: 185 186 remove_entry(e->cache, e); 187 188 e = NULL; 189/* avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */ 190 break; 191 192 case AVAHI_CACHE_VALID: 193 case AVAHI_CACHE_POOF: 194 e->state = AVAHI_CACHE_EXPIRY1; 195 percent = 85; 196 break; 197 198 case AVAHI_CACHE_EXPIRY1: 199 e->state = AVAHI_CACHE_EXPIRY2; 200 percent = 90; 201 break; 202 case AVAHI_CACHE_EXPIRY2: 203 e->state = AVAHI_CACHE_EXPIRY3; 204 percent = 95; 205 break; 206 207 case AVAHI_CACHE_EXPIRY3: 208 e->state = AVAHI_CACHE_EXPIRY_FINAL; 209 percent = 100; 210 break; 211 } 212 213 if (e) { 214 215 assert(percent > 0); 216 217 /* Request a cache update if we are subscribed to this entry */ 218 if (avahi_querier_shall_refresh_cache(e->cache->interface, e->record->key)) 219 avahi_interface_post_query(e->cache->interface, e->record->key, 0, NULL); 220 221 /* Check again later */ 222 next_expiry(e->cache, e, percent); 223 224 } 225 226/* avahi_free(txt); */ 227} 228 229static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) { 230 assert(c); 231 assert(e); 232 233 if (e->time_event) 234 avahi_time_event_update(e->time_event, &e->expiry); 235 else 236 e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e); 237} 238 239static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) { 240 AvahiUsec usec, left, right; 241 time_t now; 242 243 assert(c); 244 assert(e); 245 assert(percent > 0 && percent <= 100); 246 247 usec = (AvahiUsec) e->record->ttl * 10000; 248 249 left = usec * percent; 250 right = usec * (percent+2); /* 2% jitter */ 251 252 now = time(NULL); 253 254 if (now >= c->last_rand_timestamp + 10) { 255 c->last_rand = rand(); 256 c->last_rand_timestamp = now; 257 } 258 259 usec = left + (AvahiUsec) ((double) (right-left) * c->last_rand / (RAND_MAX+1.0)); 260 261 e->expiry = e->timestamp; 262 avahi_timeval_add(&e->expiry, usec); 263 264/* g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */ 265 266 update_time_event(c, e); 267} 268 269static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) { 270 assert(c); 271 assert(e); 272 273 e->state = state; 274 gettimeofday(&e->expiry, NULL); 275 avahi_timeval_add(&e->expiry, 1000000); /* 1s */ 276 update_time_event(c, e); 277} 278 279void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) { 280/* char *txt; */ 281 282 assert(c); 283 assert(r && r->ref >= 1); 284 285/* txt = avahi_record_to_string(r); */ 286 287 if (r->ttl == 0) { 288 /* This is a goodbye request */ 289 290 AvahiCacheEntry *e; 291 292 if ((e = lookup_record(c, r))) 293 expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL); 294 295 } else { 296 AvahiCacheEntry *e = NULL, *first; 297 struct timeval now; 298 299 gettimeofday(&now, NULL); 300 301 /* This is an update request */ 302 303 if ((first = lookup_key(c, r->key))) { 304 305 if (cache_flush) { 306 307 /* For unique entries drop all entries older than one second */ 308 for (e = first; e; e = e->by_key_next) { 309 AvahiUsec t; 310 311 t = avahi_timeval_diff(&now, &e->timestamp); 312 313 if (t > 1000000) 314 expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL); 315 } 316 } 317 318 /* Look for exactly the same entry */ 319 for (e = first; e; e = e->by_key_next) 320 if (avahi_record_equal_no_ttl(e->record, r)) 321 break; 322 } 323 324 if (e) { 325 326/* avahi_log_debug("found matching cache entry"); */ 327 328 /* We need to update the hash table key if we replace the 329 * record */ 330 if (e->by_key_prev == NULL) 331 avahi_hashmap_replace(c->hashmap, r->key, e); 332 333 /* Update the record */ 334 avahi_record_unref(e->record); 335 e->record = avahi_record_ref(r); 336 337/* avahi_log_debug("cache: updating %s", txt); */ 338 339 } else { 340 /* No entry found, therefore we create a new one */ 341 342/* avahi_log_debug("cache: couldn't find matching cache entry for %s", txt); */ 343 344 if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX) 345 return; 346 347 if (!(e = avahi_new(AvahiCacheEntry, 1))) { 348 avahi_log_error(__FILE__": Out of memory"); 349 return; 350 } 351 352 e->cache = c; 353 e->time_event = NULL; 354 e->record = avahi_record_ref(r); 355 356 /* Append to hash table */ 357 AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e); 358 avahi_hashmap_replace(c->hashmap, e->record->key, first); 359 360 /* Append to linked list */ 361 AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e); 362 363 c->n_entries++; 364 365 /* Notify subscribers */ 366 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW); 367 } 368 369 e->origin = *a; 370 e->timestamp = now; 371 next_expiry(c, e, 80); 372 e->state = AVAHI_CACHE_VALID; 373 e->cache_flush = cache_flush; 374 } 375 376/* avahi_free(txt); */ 377} 378 379struct dump_data { 380 AvahiDumpCallback callback; 381 void* userdata; 382}; 383 384static void dump_callback(void* key, void* data, void* userdata) { 385 AvahiCacheEntry *e = data; 386 AvahiKey *k = key; 387 struct dump_data *dump_data = userdata; 388 389 assert(k); 390 assert(e); 391 assert(data); 392 393 for (; e; e = e->by_key_next) { 394 char *t; 395 396 if (!(t = avahi_record_to_string(e->record))) 397 continue; /* OOM */ 398 399 dump_data->callback(t, dump_data->userdata); 400 avahi_free(t); 401 } 402} 403 404int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) { 405 struct dump_data data; 406 407 assert(c); 408 assert(callback); 409 410 callback(";;; CACHE DUMP FOLLOWS ;;;", userdata); 411 412 data.callback = callback; 413 data.userdata = userdata; 414 415 avahi_hashmap_foreach(c->hashmap, dump_callback, &data); 416 417 return 0; 418} 419 420int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) { 421 struct timeval now; 422 unsigned age; 423 424 assert(c); 425 assert(e); 426 427 gettimeofday(&now, NULL); 428 429 age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000); 430 431/* avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl); */ 432 433 return age >= e->record->ttl/2; 434} 435 436void avahi_cache_flush(AvahiCache *c) { 437 assert(c); 438 439 while (c->entries) 440 remove_entry(c, c->entries); 441} 442 443/*** Passive observation of failure ***/ 444 445static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) { 446 AvahiAddress *a = userdata; 447 struct timeval now; 448 449 assert(c); 450 assert(pattern); 451 assert(e); 452 assert(a); 453 454 gettimeofday(&now, NULL); 455 456 switch (e->state) { 457 case AVAHI_CACHE_VALID: 458 459 /* The entry was perfectly valid till, now, so let's enter 460 * POOF mode */ 461 462 e->state = AVAHI_CACHE_POOF; 463 e->poof_address = *a; 464 e->poof_timestamp = now; 465 e->poof_num = 0; 466 467 break; 468 469 case AVAHI_CACHE_POOF: 470 if (avahi_timeval_diff(&now, &e->poof_timestamp) < 1000000) 471 break; 472 473 e->poof_timestamp = now; 474 e->poof_address = *a; 475 e->poof_num ++; 476 477 /* This is the 4th time we got no response, so let's 478 * fucking remove this entry. */ 479 if (e->poof_num > 3) 480 expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL); 481 break; 482 483 default: 484 ; 485 } 486 487 return NULL; 488} 489 490void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) { 491 assert(c); 492 assert(key); 493 494 avahi_cache_walk(c, key, start_poof_callback, (void*) a); 495} 496 497void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) { 498 AvahiCacheEntry *e; 499 500 assert(c); 501 assert(record); 502 assert(a); 503 504 if (!(e = lookup_record(c, record))) 505 return; 506 507 /* This function is called for each response suppression 508 record. If the matching cache entry is in POOF state and the 509 query address is the same, we put it back into valid mode */ 510 511 if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL) 512 if (avahi_address_cmp(a, &e->poof_address) == 0) { 513 e->state = AVAHI_CACHE_VALID; 514 next_expiry(c, e, 80); 515 } 516} 517 518 519 520