]> git.meshlink.io Git - catta/blob - avahi-core/cache.c
5e87706947323d8832cd275f813ed56d8de41dfa
[catta] / avahi-core / cache.c
1 /* $Id$ */
2
3 /***
4   This file is part of avahi.
5  
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.
10  
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.
15  
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.
20 ***/
21
22 #ifdef HAVE_CONFIG_H
23 #include <config.h>
24 #endif
25
26 #include <string.h>
27 #include <stdlib.h>
28
29 #include <avahi-common/timeval.h>
30 #include <avahi-common/malloc.h>
31
32 #include "cache.h"
33 #include "log.h"
34 #include "rr-util.h"
35
36 #define AVAHI_CACHE_ENTRIES_MAX 500
37
38 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
39     AvahiCacheEntry *t;
40
41     assert(c);
42     assert(e);
43
44 /*     avahi_log_debug("removing from cache: %p %p", c, e); */
45
46     /* Remove from hash table */
47     t = avahi_hashmap_lookup(c->hashmap, e->record->key);
48     AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e);
49     if (t)
50         avahi_hashmap_replace(c->hashmap, t->record->key, t);
51     else
52         avahi_hashmap_remove(c->hashmap, e->record->key);
53
54     /* Remove from linked list */
55     AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
56         
57     if (e->time_event)
58         avahi_time_event_free(e->time_event);
59
60     avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE);
61     
62     avahi_record_unref(e->record);
63     
64     avahi_free(e);
65
66     assert(c->n_entries-- >= 1);
67 }
68
69 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
70     AvahiCache *c;
71     assert(server);
72
73     if (!(c = avahi_new(AvahiCache, 1))) {
74         avahi_log_error(__FILE__": Out of memory.");
75         return NULL; /* OOM */
76     }
77     
78     c->server = server;
79     c->interface = iface;
80
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.");
83         avahi_free(c);
84         return NULL; /* OOM */
85     }
86
87     AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
88     c->n_entries = 0;
89     
90     return c;
91 }
92
93 void avahi_cache_free(AvahiCache *c) {
94     assert(c);
95
96     while (c->entries)
97         remove_entry(c, c->entries);
98     assert(c->n_entries == 0);
99     
100     avahi_hashmap_free(c->hashmap);
101     
102     avahi_free(c);
103 }
104
105 static AvahiCacheEntry *lookup_key(AvahiCache *c, AvahiKey *k) {
106     assert(c);
107     assert(k);
108
109     assert(!avahi_key_is_pattern(k));
110     
111     return avahi_hashmap_lookup(c->hashmap, k);
112 }
113
114 void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) {
115     void* ret;
116     
117     assert(c);
118     assert(pattern);
119     assert(cb);
120     
121     if (avahi_key_is_pattern(pattern)) {
122         AvahiCacheEntry *e, *n;
123         
124         for (e = c->entries; e; e = n) {
125             n = e->entry_next;
126             
127             if (avahi_key_pattern_match(pattern, e->record->key))
128                 if ((ret = cb(c, pattern, e, userdata)))
129                     return ret;
130         }
131         
132     } else {
133         AvahiCacheEntry *e, *n;
134
135         for (e = lookup_key(c, pattern); e; e = n) {
136             n = e->by_key_next;
137                 
138             if ((ret = cb(c, pattern, e, userdata)))
139                 return ret;
140         }
141     }
142
143     return NULL;
144 }
145
146 static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
147     assert(c);
148     assert(pattern);
149     assert(e);
150
151     if (avahi_record_equal_no_ttl(e->record, userdata))
152         return e;
153
154     return NULL;
155 }
156
157 static AvahiCacheEntry *lookup_record(AvahiCache *c, AvahiRecord *r) {
158     assert(c);
159     assert(r);
160
161     return avahi_cache_walk(c, r->key, lookup_record_callback, r);
162 }
163
164 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
165
166 static void elapse_func(AvahiTimeEvent *t, void *userdata) {
167     AvahiCacheEntry *e = userdata;
168 /*     char *txt; */
169     unsigned percent = 0;
170     
171     assert(t);
172     assert(e);
173
174 /*     txt = avahi_record_to_string(e->record); */
175
176     switch (e->state) {
177
178         case AVAHI_CACHE_EXPIRY_FINAL:
179         case AVAHI_CACHE_POOF_FINAL:
180         case AVAHI_CACHE_GOODBYE_FINAL:
181         case AVAHI_CACHE_REPLACE_FINAL:
182
183             remove_entry(e->cache, e);
184             
185             e = NULL;
186 /*         avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */
187             break;
188             
189         case AVAHI_CACHE_VALID:
190         case AVAHI_CACHE_POOF:
191             e->state = AVAHI_CACHE_EXPIRY1;
192             percent = 85;
193             break;
194                 
195         case AVAHI_CACHE_EXPIRY1:
196             e->state = AVAHI_CACHE_EXPIRY2;
197             percent = 90;
198             break;
199         case AVAHI_CACHE_EXPIRY2:
200             e->state = AVAHI_CACHE_EXPIRY3;
201             percent = 95;
202             break;
203             
204         case AVAHI_CACHE_EXPIRY3:
205             e->state = AVAHI_CACHE_EXPIRY_FINAL;
206             percent = 100;
207             break;
208     }
209
210     if (e) {
211
212         assert(percent > 0);
213
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);
218         }
219         
220         /* Check again later */
221         next_expiry(e->cache, e, percent);
222         
223     }
224
225 /*     avahi_free(txt); */
226 }
227
228 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
229     assert(c);
230     assert(e);
231     
232     if (e->time_event)
233         avahi_time_event_update(e->time_event, &e->expiry);
234     else
235         e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
236 }
237
238 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
239     AvahiUsec usec, left, right;
240     
241     assert(c);
242     assert(e);
243     assert(percent > 0 && percent <= 100);
244     
245     usec = (AvahiUsec) e->record->ttl * 10000;
246
247     left = usec * percent;
248     right = usec * (percent+2); /* 2% jitter */
249
250     usec = left + (AvahiUsec) ((double) (right-left) * rand() / (RAND_MAX+1.0));
251     
252     e->expiry = e->timestamp;
253     avahi_timeval_add(&e->expiry, usec);
254     
255 /*     g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
256     
257     update_time_event(c, e);
258 }
259
260 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
261     assert(c);
262     assert(e);
263     
264     e->state = state;
265     gettimeofday(&e->expiry, NULL);
266     avahi_timeval_add(&e->expiry, 1000000); /* 1s */
267     update_time_event(c, e);
268 }
269
270 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
271 /*     char *txt; */
272     
273     assert(c);
274     assert(r && r->ref >= 1);
275
276 /*     txt = avahi_record_to_string(r); */
277
278     if (r->ttl == 0) {
279         /* This is a goodbye request */
280
281         AvahiCacheEntry *e;
282
283         if ((e = lookup_record(c, r)))
284             expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
285
286     } else {
287         AvahiCacheEntry *e = NULL, *first;
288         struct timeval now;
289
290         gettimeofday(&now, NULL);
291
292         /* This is an update request */
293
294         if ((first = lookup_key(c, r->key))) {
295             
296             if (cache_flush) {
297
298                 /* For unique entries drop all entries older than one second */
299                 for (e = first; e; e = e->by_key_next) {
300                     AvahiUsec t;
301
302                     t = avahi_timeval_diff(&now, &e->timestamp);
303
304                     if (t > 1000000)
305                         expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
306                 }
307             }
308                 
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))
312                     break;
313         }
314     
315         if (e) {
316             
317 /*             avahi_log_debug("found matching cache entry");  */
318
319             /* We need to update the hash table key if we replace the
320              * record */
321             if (e->by_key_prev == NULL)
322                 avahi_hashmap_replace(c->hashmap, r->key, e);
323             
324             /* Update the record */
325             avahi_record_unref(e->record);
326             e->record = avahi_record_ref(r);
327
328 /*             avahi_log_debug("cache: updating %s", txt);   */
329             
330         } else {
331             /* No entry found, therefore we create a new one */
332             
333 /*             avahi_log_debug("cache: couldn't find matching cache entry for %s", txt);   */
334
335             if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX)
336                 return;
337
338             if (!(e = avahi_new(AvahiCacheEntry, 1))) {
339                 avahi_log_error(__FILE__": Out of memory");
340                 return;
341             }
342
343             e->cache = c;
344             e->time_event = NULL;
345             e->record = avahi_record_ref(r);
346
347             /* Append to hash table */
348             AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
349             avahi_hashmap_replace(c->hashmap, e->record->key, first);
350
351             /* Append to linked list */
352             AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
353
354             c->n_entries++;
355
356             /* Notify subscribers */
357             avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
358         } 
359         
360         e->origin = *a;
361         e->timestamp = now;
362         next_expiry(c, e, 80);
363         e->state = AVAHI_CACHE_VALID;
364         e->cache_flush = cache_flush;
365     }
366
367 /*     avahi_free(txt);  */
368 }
369
370 struct dump_data {
371     AvahiDumpCallback callback;
372     void* userdata;
373 };
374
375 static void dump_callback(void* key, void* data, void* userdata) {
376     AvahiCacheEntry *e = data;
377     AvahiKey *k = key;
378     struct dump_data *dump_data = userdata;
379
380     assert(k);
381     assert(e);
382     assert(data);
383
384     for (; e; e = e->by_key_next) {
385         char *t;
386
387         if (!(t = avahi_record_to_string(e->record)))
388             continue; /* OOM */
389         
390         dump_data->callback(t, dump_data->userdata);
391         avahi_free(t);
392     }
393 }
394
395 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
396     struct dump_data data;
397
398     assert(c);
399     assert(callback);
400
401     callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
402
403     data.callback = callback;
404     data.userdata = userdata;
405
406     avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
407
408     return 0;
409 }
410
411 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
412     struct timeval now;
413     unsigned age;
414     
415     assert(c);
416     assert(e);
417
418     gettimeofday(&now, NULL);
419
420     age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
421
422 /*     avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl);  */
423     
424     return age >= e->record->ttl/2;
425 }
426
427 void avahi_cache_flush(AvahiCache *c) {
428     assert(c);
429
430     while (c->entries)
431         remove_entry(c, c->entries);
432 }
433
434 /*** Passive observation of failure ***/
435
436 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
437     AvahiAddress *a = userdata;
438
439     assert(c);
440     assert(pattern);
441     assert(e);
442     assert(a);
443     
444     switch (e->state) {
445         case AVAHI_CACHE_VALID:
446
447             /* The entry was perfectly valid till, now, so let's enter
448              * POOF mode */
449
450             e->state = AVAHI_CACHE_POOF;
451             e->poof_address = *a;
452             
453             break;
454
455         case AVAHI_CACHE_POOF:
456
457             /* This is the second time we got no response, so let's
458              * fucking remove this entry. */
459             
460             expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
461             break;
462
463         default:
464             ;
465     }
466     
467     return NULL;
468 }
469
470 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
471     assert(c);
472     assert(key);
473
474     avahi_cache_walk(c, key, start_poof_callback, a);
475 }
476
477 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
478     AvahiCacheEntry *e;
479
480     assert(c);
481     assert(record);
482     assert(a);
483
484     if (!(e = lookup_record(c, record)))
485         return;
486
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 */
490
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);
495         }
496 }
497
498
499