2 This file is part of avahi.
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.
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.
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
28 #include <avahi-common/timeval.h>
29 #include <avahi-common/malloc.h>
35 #define AVAHI_CACHE_ENTRIES_MAX 500
37 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
43 /* avahi_log_debug("removing from cache: %p %p", c, e); */
45 /* Remove from hash table */
46 t = avahi_hashmap_lookup(c->hashmap, e->record->key);
47 AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e);
49 avahi_hashmap_replace(c->hashmap, t->record->key, t);
51 avahi_hashmap_remove(c->hashmap, e->record->key);
53 /* Remove from linked list */
54 AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
57 avahi_time_event_free(e->time_event);
59 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE);
61 avahi_record_unref(e->record);
65 assert(c->n_entries >= 1);
69 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
73 if (!(c = avahi_new(AvahiCache, 1))) {
74 avahi_log_error(__FILE__": Out of memory.");
75 return NULL; /* OOM */
81 if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) {
82 avahi_log_error(__FILE__": Out of memory.");
84 return NULL; /* OOM */
87 AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
90 c->last_rand_timestamp = 0;
95 void avahi_cache_free(AvahiCache *c) {
99 remove_entry(c, c->entries);
100 assert(c->n_entries == 0);
102 avahi_hashmap_free(c->hashmap);
107 static AvahiCacheEntry *lookup_key(AvahiCache *c, AvahiKey *k) {
111 assert(!avahi_key_is_pattern(k));
113 return avahi_hashmap_lookup(c->hashmap, k);
116 void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) {
123 if (avahi_key_is_pattern(pattern)) {
124 AvahiCacheEntry *e, *n;
126 for (e = c->entries; e; e = n) {
129 if (avahi_key_pattern_match(pattern, e->record->key))
130 if ((ret = cb(c, pattern, e, userdata)))
135 AvahiCacheEntry *e, *n;
137 for (e = lookup_key(c, pattern); e; e = n) {
140 if ((ret = cb(c, pattern, e, userdata)))
148 static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
153 if (avahi_record_equal_no_ttl(e->record, userdata))
159 static AvahiCacheEntry *lookup_record(AvahiCache *c, AvahiRecord *r) {
163 return avahi_cache_walk(c, r->key, lookup_record_callback, r);
166 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
168 static void elapse_func(AvahiTimeEvent *t, void *userdata) {
169 AvahiCacheEntry *e = userdata;
171 unsigned percent = 0;
176 /* txt = avahi_record_to_string(e->record); */
180 case AVAHI_CACHE_EXPIRY_FINAL:
181 case AVAHI_CACHE_POOF_FINAL:
182 case AVAHI_CACHE_GOODBYE_FINAL:
183 case AVAHI_CACHE_REPLACE_FINAL:
185 remove_entry(e->cache, e);
188 /* avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */
191 case AVAHI_CACHE_VALID:
192 case AVAHI_CACHE_POOF:
193 e->state = AVAHI_CACHE_EXPIRY1;
197 case AVAHI_CACHE_EXPIRY1:
198 e->state = AVAHI_CACHE_EXPIRY2;
201 case AVAHI_CACHE_EXPIRY2:
202 e->state = AVAHI_CACHE_EXPIRY3;
206 case AVAHI_CACHE_EXPIRY3:
207 e->state = AVAHI_CACHE_EXPIRY_FINAL;
216 /* Request a cache update if we are subscribed to this entry */
217 if (avahi_querier_shall_refresh_cache(e->cache->interface, e->record->key))
218 avahi_interface_post_query(e->cache->interface, e->record->key, 0, NULL);
220 /* Check again later */
221 next_expiry(e->cache, e, percent);
225 /* avahi_free(txt); */
228 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
233 avahi_time_event_update(e->time_event, &e->expiry);
235 e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
238 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
239 AvahiUsec usec, left, right;
244 assert(percent > 0 && percent <= 100);
246 usec = (AvahiUsec) e->record->ttl * 10000;
248 left = usec * percent;
249 right = usec * (percent+2); /* 2% jitter */
253 if (now >= c->last_rand_timestamp + 10) {
254 c->last_rand = rand();
255 c->last_rand_timestamp = now;
258 usec = left + (AvahiUsec) ((double) (right-left) * c->last_rand / (RAND_MAX+1.0));
260 e->expiry = e->timestamp;
261 avahi_timeval_add(&e->expiry, usec);
263 /* g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
265 update_time_event(c, e);
268 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
273 gettimeofday(&e->expiry, NULL);
274 avahi_timeval_add(&e->expiry, 1000000); /* 1s */
275 update_time_event(c, e);
278 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
282 assert(r && r->ref >= 1);
284 /* txt = avahi_record_to_string(r); */
287 /* This is a goodbye request */
291 if ((e = lookup_record(c, r)))
292 expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
295 AvahiCacheEntry *e = NULL, *first;
298 gettimeofday(&now, NULL);
300 /* This is an update request */
302 if ((first = lookup_key(c, r->key))) {
306 /* For unique entries drop all entries older than one second */
307 for (e = first; e; e = e->by_key_next) {
310 t = avahi_timeval_diff(&now, &e->timestamp);
313 expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
317 /* Look for exactly the same entry */
318 for (e = first; e; e = e->by_key_next)
319 if (avahi_record_equal_no_ttl(e->record, r))
325 /* avahi_log_debug("found matching cache entry"); */
327 /* We need to update the hash table key if we replace the
329 if (e->by_key_prev == NULL)
330 avahi_hashmap_replace(c->hashmap, r->key, e);
332 /* Update the record */
333 avahi_record_unref(e->record);
334 e->record = avahi_record_ref(r);
336 /* avahi_log_debug("cache: updating %s", txt); */
339 /* No entry found, therefore we create a new one */
341 /* avahi_log_debug("cache: couldn't find matching cache entry for %s", txt); */
343 if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX)
346 if (!(e = avahi_new(AvahiCacheEntry, 1))) {
347 avahi_log_error(__FILE__": Out of memory");
352 e->time_event = NULL;
353 e->record = avahi_record_ref(r);
355 /* Append to hash table */
356 AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
357 avahi_hashmap_replace(c->hashmap, e->record->key, first);
359 /* Append to linked list */
360 AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
364 /* Notify subscribers */
365 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
370 next_expiry(c, e, 80);
371 e->state = AVAHI_CACHE_VALID;
372 e->cache_flush = cache_flush;
375 /* avahi_free(txt); */
379 AvahiDumpCallback callback;
383 static void dump_callback(void* key, void* data, void* userdata) {
384 AvahiCacheEntry *e = data;
386 struct dump_data *dump_data = userdata;
392 for (; e; e = e->by_key_next) {
395 if (!(t = avahi_record_to_string(e->record)))
398 dump_data->callback(t, dump_data->userdata);
403 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
404 struct dump_data data;
409 callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
411 data.callback = callback;
412 data.userdata = userdata;
414 avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
419 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
426 gettimeofday(&now, NULL);
428 age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
430 /* avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl); */
432 return age >= e->record->ttl/2;
435 void avahi_cache_flush(AvahiCache *c) {
439 remove_entry(c, c->entries);
442 /*** Passive observation of failure ***/
444 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
445 AvahiAddress *a = userdata;
453 gettimeofday(&now, NULL);
456 case AVAHI_CACHE_VALID:
458 /* The entry was perfectly valid till, now, so let's enter
461 e->state = AVAHI_CACHE_POOF;
462 e->poof_address = *a;
463 e->poof_timestamp = now;
468 case AVAHI_CACHE_POOF:
469 if (avahi_timeval_diff(&now, &e->poof_timestamp) < 1000000)
472 e->poof_timestamp = now;
473 e->poof_address = *a;
476 /* This is the 4th time we got no response, so let's
477 * fucking remove this entry. */
479 expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
489 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
493 avahi_cache_walk(c, key, start_poof_callback, (void*) a);
496 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
503 if (!(e = lookup_record(c, record)))
506 /* This function is called for each response suppression
507 record. If the matching cache entry is in POOF state and the
508 query address is the same, we put it back into valid mode */
510 if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
511 if (avahi_address_cmp(a, &e->poof_address) == 0) {
512 e->state = AVAHI_CACHE_VALID;
513 next_expiry(c, e, 80);