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
29 #include <avahi-common/timeval.h>
30 #include <avahi-common/malloc.h>
35 #define AVAHI_MAX_CACHE_ENTRIES 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);
68 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
72 if (!(c = avahi_new(AvahiCache, 1))) {
73 avahi_log_error(__FILE__": Out of memory.");
74 return NULL; /* OOM */
80 if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) {
81 avahi_log_error(__FILE__": Out of memory.");
83 return NULL; /* OOM */
86 AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
92 void avahi_cache_free(AvahiCache *c) {
96 remove_entry(c, c->entries);
97 assert(c->n_entries == 0);
99 avahi_hashmap_free(c->hashmap);
104 AvahiCacheEntry *avahi_cache_lookup_key(AvahiCache *c, AvahiKey *k) {
108 assert(!avahi_key_is_pattern(k));
110 return avahi_hashmap_lookup(c->hashmap, k);
113 void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) {
120 if (avahi_key_is_pattern(pattern)) {
121 AvahiCacheEntry *e, *n;
123 for (e = c->entries; e; e = n) {
126 if (avahi_key_pattern_match(pattern, e->record->key))
127 if ((ret = cb(c, pattern, e, userdata)))
132 AvahiCacheEntry *e, *n;
134 for (e = avahi_cache_lookup_key(c, pattern); e; e = n) {
137 if ((ret = cb(c, pattern, e, userdata)))
145 static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
150 if (avahi_record_equal_no_ttl(e->record, userdata))
156 AvahiCacheEntry *avahi_cache_lookup_record(AvahiCache *c, AvahiRecord *r) {
160 return avahi_cache_walk(c, r->key, lookup_record_callback, r);
163 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
165 static void elapse_func(AvahiTimeEvent *t, void *userdata) {
166 AvahiCacheEntry *e = userdata;
168 unsigned percent = 0;
173 /* txt = avahi_record_to_string(e->record); */
177 case AVAHI_CACHE_EXPIRY_FINAL:
178 case AVAHI_CACHE_POOF_FINAL:
179 case AVAHI_CACHE_GOODBYE_FINAL:
180 case AVAHI_CACHE_REPLACE_FINAL:
182 remove_entry(e->cache, e);
185 /* avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */
188 case AVAHI_CACHE_VALID:
189 case AVAHI_CACHE_POOF:
190 e->state = AVAHI_CACHE_EXPIRY1;
194 case AVAHI_CACHE_EXPIRY1:
195 e->state = AVAHI_CACHE_EXPIRY2;
198 case AVAHI_CACHE_EXPIRY2:
199 e->state = AVAHI_CACHE_EXPIRY3;
203 case AVAHI_CACHE_EXPIRY3:
204 e->state = AVAHI_CACHE_EXPIRY_FINAL;
213 /* Request a cache update, if we are subscribed to this entry */
214 if (avahi_querier_exists(e->cache->interface, e->record->key)) {
215 /* avahi_log_debug("Requesting cache entry update at %i%% for %s.", percent, txt); */
216 avahi_interface_post_query(e->cache->interface, e->record->key, 1);
219 /* Check again later */
220 next_expiry(e->cache, e, percent);
224 /* avahi_free(txt); */
227 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
232 avahi_time_event_update(e->time_event, &e->expiry);
234 e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
237 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
238 AvahiUsec usec, left, right;
242 assert(percent > 0 && percent <= 100);
244 usec = (AvahiUsec) e->record->ttl * 10000;
246 left = usec * percent;
247 right = usec * (percent+2); /* 2% jitter */
249 usec = left + (AvahiUsec) ((double) (right-left) * rand() / (RAND_MAX+1.0));
251 e->expiry = e->timestamp;
252 avahi_timeval_add(&e->expiry, usec);
254 /* g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
256 update_time_event(c, e);
259 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
264 gettimeofday(&e->expiry, NULL);
265 avahi_timeval_add(&e->expiry, 1000000); /* 1s */
266 update_time_event(c, e);
269 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
273 assert(r && r->ref >= 1);
275 /* txt = avahi_record_to_string(r); */
278 /* This is a goodbye request */
282 if ((e = avahi_cache_lookup_record(c, r)))
283 expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
286 AvahiCacheEntry *e = NULL, *first;
289 gettimeofday(&now, NULL);
291 /* This is an update request */
293 if ((first = avahi_cache_lookup_key(c, r->key))) {
297 /* For unique entries drop all entries older than one second */
298 for (e = first; e; e = e->by_key_next) {
301 t = avahi_timeval_diff(&now, &e->timestamp);
304 expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
308 /* Look for exactly the same entry */
309 for (e = first; e; e = e->by_key_next)
310 if (avahi_record_equal_no_ttl(e->record, r))
316 /* avahi_log_debug("found matching cache entry"); */
318 /* We need to update the hash table key if we replace the
320 if (e->by_key_prev == NULL)
321 avahi_hashmap_replace(c->hashmap, r->key, e);
323 /* Update the record */
324 avahi_record_unref(e->record);
325 e->record = avahi_record_ref(r);
327 /* avahi_log_debug("cache: updating %s", txt); */
330 /* No entry found, therefore we create a new one */
332 /* avahi_log_debug("cache: couldn't find matching cache entry for %s", txt); */
334 if (c->n_entries >= AVAHI_MAX_CACHE_ENTRIES)
337 if (!(e = avahi_new(AvahiCacheEntry, 1))) {
338 avahi_log_error(__FILE__": Out of memory");
343 e->time_event = NULL;
344 e->record = avahi_record_ref(r);
346 /* Append to hash table */
347 AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
348 avahi_hashmap_replace(c->hashmap, e->record->key, first);
350 /* Append to linked list */
351 AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
355 /* Notify subscribers */
356 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
361 next_expiry(c, e, 80);
362 e->state = AVAHI_CACHE_VALID;
363 e->cache_flush = cache_flush;
366 /* avahi_free(txt); */
370 AvahiDumpCallback callback;
374 static void dump_callback(void* key, void* data, void* userdata) {
375 AvahiCacheEntry *e = data;
377 struct dump_data *dump_data = userdata;
383 for (; e; e = e->by_key_next) {
386 if (!(t = avahi_record_to_string(e->record)))
389 dump_data->callback(t, dump_data->userdata);
394 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
395 struct dump_data data;
400 callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
402 data.callback = callback;
403 data.userdata = userdata;
405 avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
410 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
417 gettimeofday(&now, NULL);
419 age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
421 /* avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl); */
423 return age >= e->record->ttl/2;
426 void avahi_cache_flush(AvahiCache *c) {
430 remove_entry(c, c->entries);
433 /*** Passive observation of failure ***/
435 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
436 AvahiAddress *a = userdata;
444 case AVAHI_CACHE_VALID:
446 /* The entry was perfectly valid till, now, so let's enter
449 e->state = AVAHI_CACHE_POOF;
450 e->poof_address = *a;
454 case AVAHI_CACHE_POOF:
456 /* This is the second time we got no response, so let's
457 * fucking remove this entry. */
459 expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
469 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
473 avahi_cache_walk(c, key, start_poof_callback, a);
476 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
483 if (!(e = avahi_cache_lookup_record(c, record)))
486 /* This function is called for each response suppression
487 record. If the matching cache entry is in POOF state and the
488 query address is the same, we put it back into valid mode */
490 if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
491 if (avahi_address_cmp(a, &e->poof_address) == 0) {
492 e->state = AVAHI_CACHE_VALID;
493 next_expiry(c, e, 80);