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>
36 #define AVAHI_CACHE_ENTRIES_MAX 500
38 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
44 /* avahi_log_debug("removing from cache: %p %p", c, e); */
46 /* Remove from hash table */
47 t = avahi_hashmap_lookup(c->hashmap, e->record->key);
48 AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e);
50 avahi_hashmap_replace(c->hashmap, t->record->key, t);
52 avahi_hashmap_remove(c->hashmap, e->record->key);
54 /* Remove from linked list */
55 AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
58 avahi_time_event_free(e->time_event);
60 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE);
62 avahi_record_unref(e->record);
66 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);
93 void avahi_cache_free(AvahiCache *c) {
97 remove_entry(c, c->entries);
98 assert(c->n_entries == 0);
100 avahi_hashmap_free(c->hashmap);
105 static AvahiCacheEntry *lookup_key(AvahiCache *c, AvahiKey *k) {
109 assert(!avahi_key_is_pattern(k));
111 return avahi_hashmap_lookup(c->hashmap, k);
114 void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) {
121 if (avahi_key_is_pattern(pattern)) {
122 AvahiCacheEntry *e, *n;
124 for (e = c->entries; e; e = n) {
127 if (avahi_key_pattern_match(pattern, e->record->key))
128 if ((ret = cb(c, pattern, e, userdata)))
133 AvahiCacheEntry *e, *n;
135 for (e = lookup_key(c, pattern); e; e = n) {
138 if ((ret = cb(c, pattern, e, userdata)))
146 static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
151 if (avahi_record_equal_no_ttl(e->record, userdata))
157 static AvahiCacheEntry *lookup_record(AvahiCache *c, AvahiRecord *r) {
161 return avahi_cache_walk(c, r->key, lookup_record_callback, r);
164 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
166 static void elapse_func(AvahiTimeEvent *t, void *userdata) {
167 AvahiCacheEntry *e = userdata;
169 unsigned percent = 0;
174 /* txt = avahi_record_to_string(e->record); */
178 case AVAHI_CACHE_EXPIRY_FINAL:
179 case AVAHI_CACHE_POOF_FINAL:
180 case AVAHI_CACHE_GOODBYE_FINAL:
181 case AVAHI_CACHE_REPLACE_FINAL:
183 remove_entry(e->cache, e);
186 /* avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */
189 case AVAHI_CACHE_VALID:
190 case AVAHI_CACHE_POOF:
191 e->state = AVAHI_CACHE_EXPIRY1;
195 case AVAHI_CACHE_EXPIRY1:
196 e->state = AVAHI_CACHE_EXPIRY2;
199 case AVAHI_CACHE_EXPIRY2:
200 e->state = AVAHI_CACHE_EXPIRY3;
204 case AVAHI_CACHE_EXPIRY3:
205 e->state = AVAHI_CACHE_EXPIRY_FINAL;
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);
218 /* Check again later */
219 next_expiry(e->cache, e, percent);
223 /* avahi_free(txt); */
226 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
231 avahi_time_event_update(e->time_event, &e->expiry);
233 e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
236 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
237 AvahiUsec usec, left, right;
241 assert(percent > 0 && percent <= 100);
243 usec = (AvahiUsec) e->record->ttl * 10000;
245 left = usec * percent;
246 right = usec * (percent+2); /* 2% jitter */
248 usec = left + (AvahiUsec) ((double) (right-left) * rand() / (RAND_MAX+1.0));
250 e->expiry = e->timestamp;
251 avahi_timeval_add(&e->expiry, usec);
253 /* g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
255 update_time_event(c, e);
258 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
263 gettimeofday(&e->expiry, NULL);
264 avahi_timeval_add(&e->expiry, 1000000); /* 1s */
265 update_time_event(c, e);
268 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
272 assert(r && r->ref >= 1);
274 /* txt = avahi_record_to_string(r); */
277 /* This is a goodbye request */
281 if ((e = lookup_record(c, r)))
282 expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
285 AvahiCacheEntry *e = NULL, *first;
288 gettimeofday(&now, NULL);
290 /* This is an update request */
292 if ((first = lookup_key(c, r->key))) {
296 /* For unique entries drop all entries older than one second */
297 for (e = first; e; e = e->by_key_next) {
300 t = avahi_timeval_diff(&now, &e->timestamp);
303 expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
307 /* Look for exactly the same entry */
308 for (e = first; e; e = e->by_key_next)
309 if (avahi_record_equal_no_ttl(e->record, r))
315 /* avahi_log_debug("found matching cache entry"); */
317 /* We need to update the hash table key if we replace the
319 if (e->by_key_prev == NULL)
320 avahi_hashmap_replace(c->hashmap, r->key, e);
322 /* Update the record */
323 avahi_record_unref(e->record);
324 e->record = avahi_record_ref(r);
326 /* avahi_log_debug("cache: updating %s", txt); */
329 /* No entry found, therefore we create a new one */
331 /* avahi_log_debug("cache: couldn't find matching cache entry for %s", txt); */
333 if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX)
336 if (!(e = avahi_new(AvahiCacheEntry, 1))) {
337 avahi_log_error(__FILE__": Out of memory");
342 e->time_event = NULL;
343 e->record = avahi_record_ref(r);
345 /* Append to hash table */
346 AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
347 avahi_hashmap_replace(c->hashmap, e->record->key, first);
349 /* Append to linked list */
350 AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
354 /* Notify subscribers */
355 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
360 next_expiry(c, e, 80);
361 e->state = AVAHI_CACHE_VALID;
362 e->cache_flush = cache_flush;
365 /* avahi_free(txt); */
369 AvahiDumpCallback callback;
373 static void dump_callback(void* key, void* data, void* userdata) {
374 AvahiCacheEntry *e = data;
376 struct dump_data *dump_data = userdata;
382 for (; e; e = e->by_key_next) {
385 if (!(t = avahi_record_to_string(e->record)))
388 dump_data->callback(t, dump_data->userdata);
393 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
394 struct dump_data data;
399 callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
401 data.callback = callback;
402 data.userdata = userdata;
404 avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
409 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
416 gettimeofday(&now, NULL);
418 age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
420 /* avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl); */
422 return age >= e->record->ttl/2;
425 void avahi_cache_flush(AvahiCache *c) {
429 remove_entry(c, c->entries);
432 /*** Passive observation of failure ***/
434 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
435 AvahiAddress *a = userdata;
443 case AVAHI_CACHE_VALID:
445 /* The entry was perfectly valid till, now, so let's enter
448 e->state = AVAHI_CACHE_POOF;
449 e->poof_address = *a;
453 case AVAHI_CACHE_POOF:
455 /* This is the second time we got no response, so let's
456 * fucking remove this entry. */
458 expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
468 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
472 avahi_cache_walk(c, key, start_poof_callback, a);
475 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
482 if (!(e = lookup_record(c, record)))
485 /* This function is called for each response suppression
486 record. If the matching cache entry is in POOF state and the
487 query address is the same, we put it back into valid mode */
489 if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
490 if (avahi_address_cmp(a, &e->poof_address) == 0) {
491 e->state = AVAHI_CACHE_VALID;
492 next_expiry(c, e, 80);