Lines Matching defs:*
0 /* $Id$ */
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
19 USA.
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif
26 #include <string.h>
27 #include <stdlib.h>
28 #include <time.h>
30 #include <avahi-common/timeval.h>
31 #include <avahi-common/malloc.h>
33 #include "cache.h"
34 #include "log.h"
35 #include "rr-util.h"
37 #define AVAHI_CACHE_ENTRIES_MAX 500
39 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
40 AvahiCacheEntry *t;
42 assert(c);
43 assert(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);
50 if (t)
51 avahi_hashmap_replace(c->hashmap, t->record->key, t);
52 else
53 avahi_hashmap_remove(c->hashmap, e->record->key);
55 /* Remove from linked list */
56 AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
58 if (e->time_event)
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);
65 avahi_free(e);
67 assert(c->n_entries-- >= 1);
70 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
71 AvahiCache *c;
72 assert(server);
74 if (!(c = avahi_new(AvahiCache, 1))) {
75 avahi_log_error(__FILE__": Out of memory.");
76 return NULL; /* OOM */
79 c->server = server;
80 c->interface = iface;
82 if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) {
83 avahi_log_error(__FILE__": Out of memory.");
84 avahi_free(c);
85 return NULL; /* OOM */
88 AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
89 c->n_entries = 0;
91 c->last_rand_timestamp = 0;
93 return c;
96 void avahi_cache_free(AvahiCache *c) {
97 assert(c);
99 while (c->entries)
100 remove_entry(c, c->entries);
101 assert(c->n_entries == 0);
103 avahi_hashmap_free(c->hashmap);
105 avahi_free(c);
108 static AvahiCacheEntry *lookup_key(AvahiCache *c, AvahiKey *k) {
109 assert(c);
110 assert(k);
112 assert(!avahi_key_is_pattern(k));
114 return avahi_hashmap_lookup(c->hashmap, k);
117 void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) {
118 void* ret;
120 assert(c);
121 assert(pattern);
122 assert(cb);
124 if (avahi_key_is_pattern(pattern)) {
125 AvahiCacheEntry *e, *n;
127 for (e = c->entries; e; e = n) {
128 n = e->entry_next;
130 if (avahi_key_pattern_match(pattern, e->record->key))
131 if ((ret = cb(c, pattern, e, userdata)))
132 return ret;
135 } else {
136 AvahiCacheEntry *e, *n;
138 for (e = lookup_key(c, pattern); e; e = n) {
139 n = e->by_key_next;
141 if ((ret = cb(c, pattern, e, userdata)))
142 return ret;
146 return NULL;
149 static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
150 assert(c);
151 assert(pattern);
152 assert(e);
154 if (avahi_record_equal_no_ttl(e->record, userdata))
155 return e;
157 return NULL;
160 static AvahiCacheEntry *lookup_record(AvahiCache *c, AvahiRecord *r) {
161 assert(c);
162 assert(r);
164 return avahi_cache_walk(c, r->key, lookup_record_callback, r);
167 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
169 static void elapse_func(AvahiTimeEvent *t, void *userdata) {
170 AvahiCacheEntry *e = userdata;
171 /* char *txt; */
172 unsigned percent = 0;
174 assert(t);
175 assert(e);
177 /* txt = avahi_record_to_string(e->record); */
179 switch (e->state) {
181 case AVAHI_CACHE_EXPIRY_FINAL:
182 case AVAHI_CACHE_POOF_FINAL:
183 case AVAHI_CACHE_GOODBYE_FINAL:
184 case AVAHI_CACHE_REPLACE_FINAL:
186 remove_entry(e->cache, e);
188 e = NULL;
189 /* avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */
190 break;
192 case AVAHI_CACHE_VALID:
193 case AVAHI_CACHE_POOF:
194 e->state = AVAHI_CACHE_EXPIRY1;
195 percent = 85;
196 break;
198 case AVAHI_CACHE_EXPIRY1:
199 e->state = AVAHI_CACHE_EXPIRY2;
200 percent = 90;
201 break;
202 case AVAHI_CACHE_EXPIRY2:
203 e->state = AVAHI_CACHE_EXPIRY3;
204 percent = 95;
205 break;
207 case AVAHI_CACHE_EXPIRY3:
208 e->state = AVAHI_CACHE_EXPIRY_FINAL;
209 percent = 100;
210 break;
213 if (e) {
215 assert(percent > 0);
217 /* Request a cache update if we are subscribed to this entry */
218 if (avahi_querier_shall_refresh_cache(e->cache->interface, e->record->key))
219 avahi_interface_post_query(e->cache->interface, e->record->key, 0, NULL);
221 /* Check again later */
222 next_expiry(e->cache, e, percent);
226 /* avahi_free(txt); */
229 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
230 assert(c);
231 assert(e);
233 if (e->time_event)
234 avahi_time_event_update(e->time_event, &e->expiry);
235 else
236 e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
239 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
240 AvahiUsec usec, left, right;
241 time_t now;
243 assert(c);
244 assert(e);
245 assert(percent > 0 && percent <= 100);
247 usec = (AvahiUsec) e->record->ttl * 10000;
249 left = usec * percent;
250 right = usec * (percent+2); /* 2% jitter */
252 now = time(NULL);
254 if (now >= c->last_rand_timestamp + 10) {
255 c->last_rand = rand();
256 c->last_rand_timestamp = now;
259 usec = left + (AvahiUsec) ((double) (right-left) * c->last_rand / (RAND_MAX+1.0));
261 e->expiry = e->timestamp;
262 avahi_timeval_add(&e->expiry, usec);
264 /* g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
266 update_time_event(c, e);
269 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
270 assert(c);
271 assert(e);
273 e->state = state;
274 gettimeofday(&e->expiry, NULL);
275 avahi_timeval_add(&e->expiry, 1000000); /* 1s */
276 update_time_event(c, e);
279 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
280 /* char *txt; */
282 assert(c);
283 assert(r && r->ref >= 1);
285 /* txt = avahi_record_to_string(r); */
287 if (r->ttl == 0) {
288 /* This is a goodbye request */
290 AvahiCacheEntry *e;
292 if ((e = lookup_record(c, r)))
293 expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
295 } else {
296 AvahiCacheEntry *e = NULL, *first;
297 struct timeval now;
299 gettimeofday(&now, NULL);
301 /* This is an update request */
303 if ((first = lookup_key(c, r->key))) {
305 if (cache_flush) {
307 /* For unique entries drop all entries older than one second */
308 for (e = first; e; e = e->by_key_next) {
309 AvahiUsec t;
311 t = avahi_timeval_diff(&now, &e->timestamp);
313 if (t > 1000000)
314 expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
318 /* Look for exactly the same entry */
319 for (e = first; e; e = e->by_key_next)
320 if (avahi_record_equal_no_ttl(e->record, r))
321 break;
324 if (e) {
326 /* avahi_log_debug("found matching cache entry"); */
328 /* We need to update the hash table key if we replace the
329 * record */
330 if (e->by_key_prev == NULL)
331 avahi_hashmap_replace(c->hashmap, r->key, e);
333 /* Update the record */
334 avahi_record_unref(e->record);
335 e->record = avahi_record_ref(r);
337 /* avahi_log_debug("cache: updating %s", txt); */
339 } else {
340 /* No entry found, therefore we create a new one */
342 /* avahi_log_debug("cache: couldn't find matching cache entry for %s", txt); */
344 if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX)
345 return;
347 if (!(e = avahi_new(AvahiCacheEntry, 1))) {
348 avahi_log_error(__FILE__": Out of memory");
349 return;
352 e->cache = c;
353 e->time_event = NULL;
354 e->record = avahi_record_ref(r);
356 /* Append to hash table */
357 AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
358 avahi_hashmap_replace(c->hashmap, e->record->key, first);
360 /* Append to linked list */
361 AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
363 c->n_entries++;
365 /* Notify subscribers */
366 avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
369 e->origin = *a;
370 e->timestamp = now;
371 next_expiry(c, e, 80);
372 e->state = AVAHI_CACHE_VALID;
373 e->cache_flush = cache_flush;
376 /* avahi_free(txt); */
379 struct dump_data {
380 AvahiDumpCallback callback;
381 void* userdata;
384 static void dump_callback(void* key, void* data, void* userdata) {
385 AvahiCacheEntry *e = data;
386 AvahiKey *k = key;
387 struct dump_data *dump_data = userdata;
389 assert(k);
390 assert(e);
391 assert(data);
393 for (; e; e = e->by_key_next) {
394 char *t;
396 if (!(t = avahi_record_to_string(e->record)))
397 continue; /* OOM */
399 dump_data->callback(t, dump_data->userdata);
400 avahi_free(t);
404 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
405 struct dump_data data;
407 assert(c);
408 assert(callback);
410 callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
412 data.callback = callback;
413 data.userdata = userdata;
415 avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
417 return 0;
420 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
421 struct timeval now;
422 unsigned age;
424 assert(c);
425 assert(e);
427 gettimeofday(&now, NULL);
429 age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
431 /* avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl); */
433 return age >= e->record->ttl/2;
436 void avahi_cache_flush(AvahiCache *c) {
437 assert(c);
439 while (c->entries)
440 remove_entry(c, c->entries);
443 /*** Passive observation of failure ***/
445 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
446 AvahiAddress *a = userdata;
447 struct timeval now;
449 assert(c);
450 assert(pattern);
451 assert(e);
452 assert(a);
454 gettimeofday(&now, NULL);
456 switch (e->state) {
457 case AVAHI_CACHE_VALID:
459 /* The entry was perfectly valid till, now, so let's enter
460 * POOF mode */
462 e->state = AVAHI_CACHE_POOF;
463 e->poof_address = *a;
464 e->poof_timestamp = now;
465 e->poof_num = 0;
467 break;
469 case AVAHI_CACHE_POOF:
470 if (avahi_timeval_diff(&now, &e->poof_timestamp) < 1000000)
471 break;
473 e->poof_timestamp = now;
474 e->poof_address = *a;
475 e->poof_num ++;
477 /* This is the 4th time we got no response, so let's
478 * fucking remove this entry. */
479 if (e->poof_num > 3)
480 expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
481 break;
483 default:
487 return NULL;
490 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
491 assert(c);
492 assert(key);
494 avahi_cache_walk(c, key, start_poof_callback, (void*) a);
497 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
498 AvahiCacheEntry *e;
500 assert(c);
501 assert(record);
502 assert(a);
504 if (!(e = lookup_record(c, record)))
505 return;
507 /* This function is called for each response suppression
508 record. If the matching cache entry is in POOF state and the
509 query address is the same, we put it back into valid mode */
511 if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
512 if (avahi_address_cmp(a, &e->poof_address) == 0) {
513 e->state = AVAHI_CACHE_VALID;
514 next_expiry(c, e, 80);