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_exists(e->cache->interface, e->record->key)) {
216 /* avahi_log_debug("Requesting cache entry update at %i%% for %s.", percent, txt); */
217 avahi_interface_post_query(e->cache->interface, e->record->key, 1);
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;
243 assert(percent > 0 && percent <= 100);
245 usec = (AvahiUsec) e->record->ttl * 10000;
247 left = usec * percent;
248 right = usec * (percent+2); /* 2% jitter */
250 usec = left + (AvahiUsec) ((double) (right-left) * rand() / (RAND_MAX+1.0));
252 e->expiry = e->timestamp;
253 avahi_timeval_add(&e->expiry, usec);
255 /* g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
257 update_time_event(c, e);
260 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
265 gettimeofday(&e->expiry, NULL);
266 avahi_timeval_add(&e->expiry, 1000000); /* 1s */
267 update_time_event(c, e);
270 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
274 assert(r && r->ref >= 1);
276 /* txt = avahi_record_to_string(r); */
279 /* This is a goodbye request */
283 if ((e = lookup_record(c, r)))
284 expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
287 AvahiCacheEntry *e = NULL, *first;
290 gettimeofday(&now, NULL);
292 /* This is an update request */
294 if ((first = lookup_key(c, r->key))) {
298 /* For unique entries drop all entries older than one second */
299 for (e = first; e; e = e->by_key_next) {
302 t = avahi_timeval_diff(&now, &e->timestamp);
305 expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
309 /* Look for exactly the same entry */
310 for (e = first; e; e = e->by_key_next)
311 if (avahi_record_equal_no_ttl(e->record, r))
317 /* avahi_log_debug("found matching cache entry"); */
319 /* We need to update the hash table key if we replace the
321 if (e->by_key_prev == NULL)
322 avahi_hashmap_replace(c->hashmap, r->key, e);
324 /* Update the record */
325 avahi_record_unref(e->record);
326 e->record = avahi_record_ref(r);
328 /* avahi_log_debug("cache: updating %s", txt); */
331 /* No entry found, therefore we create a new one */
333 /* avahi_log_debug("cache: couldn't find matching cache entry for %s", txt); */
335 if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX)
338 if (!(e = avahi_new(AvahiCacheEntry, 1))) {
339 avahi_log_error(__FILE__": Out of memory");
344 e->time_event = NULL;
345 e->record = avahi_record_ref(r);
347 /* Append to hash table */
348 AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
349 avahi_hashmap_replace(c->hashmap, e->record->key, first);
351 /* Append to linked list */
352 AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
356 /* Notify subscribers */
357 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
362 next_expiry(c, e, 80);
363 e->state = AVAHI_CACHE_VALID;
364 e->cache_flush = cache_flush;
367 /* avahi_free(txt); */
371 AvahiDumpCallback callback;
375 static void dump_callback(void* key, void* data, void* userdata) {
376 AvahiCacheEntry *e = data;
378 struct dump_data *dump_data = userdata;
384 for (; e; e = e->by_key_next) {
387 if (!(t = avahi_record_to_string(e->record)))
390 dump_data->callback(t, dump_data->userdata);
395 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
396 struct dump_data data;
401 callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
403 data.callback = callback;
404 data.userdata = userdata;
406 avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
411 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
418 gettimeofday(&now, NULL);
420 age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
422 /* avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl); */
424 return age >= e->record->ttl/2;
427 void avahi_cache_flush(AvahiCache *c) {
431 remove_entry(c, c->entries);
434 /*** Passive observation of failure ***/
436 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
437 AvahiAddress *a = userdata;
445 case AVAHI_CACHE_VALID:
447 /* The entry was perfectly valid till, now, so let's enter
450 e->state = AVAHI_CACHE_POOF;
451 e->poof_address = *a;
455 case AVAHI_CACHE_POOF:
457 /* This is the second time we got no response, so let's
458 * fucking remove this entry. */
460 expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
470 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
474 avahi_cache_walk(c, key, start_poof_callback, a);
477 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
484 if (!(e = lookup_record(c, record)))
487 /* This function is called for each response suppression
488 record. If the matching cache entry is in POOF state and the
489 query address is the same, we put it back into valid mode */
491 if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
492 if (avahi_address_cmp(a, &e->poof_address) == 0) {
493 e->state = AVAHI_CACHE_VALID;
494 next_expiry(c, e, 80);