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