4 This file is part of avahi.
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.
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.
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
30 #include <avahi-common/timeval.h>
31 #include <avahi-common/malloc.h>
37 #define AVAHI_CACHE_ENTRIES_MAX 500
39 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
45 /* avahi_log_debug("removing from cache: %p %p", c, e); */
47 /* Remove from hash table */
48 t = avahi_hashmap_lookup(c->hashmap, e->record->key);
49 AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e);
51 avahi_hashmap_replace(c->hashmap, t->record->key, t);
53 avahi_hashmap_remove(c->hashmap, e->record->key);
55 /* Remove from linked list */
56 AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
59 avahi_time_event_free(e->time_event);
61 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE);
63 avahi_record_unref(e->record);
67 assert(c->n_entries >= 1);
71 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
75 if (!(c = avahi_new(AvahiCache, 1))) {
76 avahi_log_error(__FILE__": Out of memory.");
77 return NULL; /* OOM */
83 if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) {
84 avahi_log_error(__FILE__": Out of memory.");
86 return NULL; /* OOM */
89 AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
92 c->last_rand_timestamp = 0;
97 void avahi_cache_free(AvahiCache *c) {
101 remove_entry(c, c->entries);
102 assert(c->n_entries == 0);
104 avahi_hashmap_free(c->hashmap);
109 static AvahiCacheEntry *lookup_key(AvahiCache *c, AvahiKey *k) {
113 assert(!avahi_key_is_pattern(k));
115 return avahi_hashmap_lookup(c->hashmap, k);
118 void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) {
125 if (avahi_key_is_pattern(pattern)) {
126 AvahiCacheEntry *e, *n;
128 for (e = c->entries; e; e = n) {
131 if (avahi_key_pattern_match(pattern, e->record->key))
132 if ((ret = cb(c, pattern, e, userdata)))
137 AvahiCacheEntry *e, *n;
139 for (e = lookup_key(c, pattern); e; e = n) {
142 if ((ret = cb(c, pattern, e, userdata)))
150 static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
155 if (avahi_record_equal_no_ttl(e->record, userdata))
161 static AvahiCacheEntry *lookup_record(AvahiCache *c, AvahiRecord *r) {
165 return avahi_cache_walk(c, r->key, lookup_record_callback, r);
168 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
170 static void elapse_func(AvahiTimeEvent *t, void *userdata) {
171 AvahiCacheEntry *e = userdata;
173 unsigned percent = 0;
178 /* txt = avahi_record_to_string(e->record); */
182 case AVAHI_CACHE_EXPIRY_FINAL:
183 case AVAHI_CACHE_POOF_FINAL:
184 case AVAHI_CACHE_GOODBYE_FINAL:
185 case AVAHI_CACHE_REPLACE_FINAL:
187 remove_entry(e->cache, e);
190 /* avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */
193 case AVAHI_CACHE_VALID:
194 case AVAHI_CACHE_POOF:
195 e->state = AVAHI_CACHE_EXPIRY1;
199 case AVAHI_CACHE_EXPIRY1:
200 e->state = AVAHI_CACHE_EXPIRY2;
203 case AVAHI_CACHE_EXPIRY2:
204 e->state = AVAHI_CACHE_EXPIRY3;
208 case AVAHI_CACHE_EXPIRY3:
209 e->state = AVAHI_CACHE_EXPIRY_FINAL;
218 /* Request a cache update if we are subscribed to this entry */
219 if (avahi_querier_shall_refresh_cache(e->cache->interface, e->record->key))
220 avahi_interface_post_query(e->cache->interface, e->record->key, 0, NULL);
222 /* Check again later */
223 next_expiry(e->cache, e, percent);
227 /* avahi_free(txt); */
230 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
235 avahi_time_event_update(e->time_event, &e->expiry);
237 e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
240 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
241 AvahiUsec usec, left, right;
246 assert(percent > 0 && percent <= 100);
248 usec = (AvahiUsec) e->record->ttl * 10000;
250 left = usec * percent;
251 right = usec * (percent+2); /* 2% jitter */
255 if (now >= c->last_rand_timestamp + 10) {
256 c->last_rand = rand();
257 c->last_rand_timestamp = now;
260 usec = left + (AvahiUsec) ((double) (right-left) * c->last_rand / (RAND_MAX+1.0));
262 e->expiry = e->timestamp;
263 avahi_timeval_add(&e->expiry, usec);
265 /* g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
267 update_time_event(c, e);
270 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
275 gettimeofday(&e->expiry, NULL);
276 avahi_timeval_add(&e->expiry, 1000000); /* 1s */
277 update_time_event(c, e);
280 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
284 assert(r && r->ref >= 1);
286 /* txt = avahi_record_to_string(r); */
289 /* This is a goodbye request */
293 if ((e = lookup_record(c, r)))
294 expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
297 AvahiCacheEntry *e = NULL, *first;
300 gettimeofday(&now, NULL);
302 /* This is an update request */
304 if ((first = lookup_key(c, r->key))) {
308 /* For unique entries drop all entries older than one second */
309 for (e = first; e; e = e->by_key_next) {
312 t = avahi_timeval_diff(&now, &e->timestamp);
315 expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
319 /* Look for exactly the same entry */
320 for (e = first; e; e = e->by_key_next)
321 if (avahi_record_equal_no_ttl(e->record, r))
327 /* avahi_log_debug("found matching cache entry"); */
329 /* We need to update the hash table key if we replace the
331 if (e->by_key_prev == NULL)
332 avahi_hashmap_replace(c->hashmap, r->key, e);
334 /* Update the record */
335 avahi_record_unref(e->record);
336 e->record = avahi_record_ref(r);
338 /* avahi_log_debug("cache: updating %s", txt); */
341 /* No entry found, therefore we create a new one */
343 /* avahi_log_debug("cache: couldn't find matching cache entry for %s", txt); */
345 if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX)
348 if (!(e = avahi_new(AvahiCacheEntry, 1))) {
349 avahi_log_error(__FILE__": Out of memory");
354 e->time_event = NULL;
355 e->record = avahi_record_ref(r);
357 /* Append to hash table */
358 AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
359 avahi_hashmap_replace(c->hashmap, e->record->key, first);
361 /* Append to linked list */
362 AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
366 /* Notify subscribers */
367 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
372 next_expiry(c, e, 80);
373 e->state = AVAHI_CACHE_VALID;
374 e->cache_flush = cache_flush;
377 /* avahi_free(txt); */
381 AvahiDumpCallback callback;
385 static void dump_callback(void* key, void* data, void* userdata) {
386 AvahiCacheEntry *e = data;
388 struct dump_data *dump_data = userdata;
394 for (; e; e = e->by_key_next) {
397 if (!(t = avahi_record_to_string(e->record)))
400 dump_data->callback(t, dump_data->userdata);
405 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
406 struct dump_data data;
411 callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
413 data.callback = callback;
414 data.userdata = userdata;
416 avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
421 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
428 gettimeofday(&now, NULL);
430 age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
432 /* avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl); */
434 return age >= e->record->ttl/2;
437 void avahi_cache_flush(AvahiCache *c) {
441 remove_entry(c, c->entries);
444 /*** Passive observation of failure ***/
446 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
447 AvahiAddress *a = userdata;
455 gettimeofday(&now, NULL);
458 case AVAHI_CACHE_VALID:
460 /* The entry was perfectly valid till, now, so let's enter
463 e->state = AVAHI_CACHE_POOF;
464 e->poof_address = *a;
465 e->poof_timestamp = now;
470 case AVAHI_CACHE_POOF:
471 if (avahi_timeval_diff(&now, &e->poof_timestamp) < 1000000)
474 e->poof_timestamp = now;
475 e->poof_address = *a;
478 /* This is the 4th time we got no response, so let's
479 * fucking remove this entry. */
481 expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
491 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
495 avahi_cache_walk(c, key, start_poof_callback, (void*) a);
498 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
505 if (!(e = lookup_record(c, record)))
508 /* This function is called for each response suppression
509 record. If the matching cache entry is in POOF state and the
510 query address is the same, we put it back into valid mode */
512 if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
513 if (avahi_address_cmp(a, &e->poof_address) == 0) {
514 e->state = AVAHI_CACHE_VALID;
515 next_expiry(c, e, 80);