]> git.meshlink.io Git - catta/blob - avahi-core/cache.c
454aac53a5efa068be431b00285b068373d93ea4
[catta] / avahi-core / cache.c
1 /***
2   This file is part of avahi.
3
4   avahi is free software; you can redistribute it and/or modify it
5   under the terms of the GNU Lesser General Public License as
6   published by the Free Software Foundation; either version 2.1 of the
7   License, or (at your option) any later version.
8
9   avahi is distributed in the hope that it will be useful, but WITHOUT
10   ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
11   or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General
12   Public License for more details.
13
14   You should have received a copy of the GNU Lesser General Public
15   License along with avahi; if not, write to the Free Software
16   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307
17   USA.
18 ***/
19
20 #ifdef HAVE_CONFIG_H
21 #include <config.h>
22 #endif
23
24 #include <string.h>
25 #include <stdlib.h>
26 #include <time.h>
27
28 #include <avahi-common/timeval.h>
29 #include <avahi-common/malloc.h>
30
31 #include "cache.h"
32 #include "log.h"
33 #include "rr-util.h"
34
35 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
36     AvahiCacheEntry *t;
37
38     assert(c);
39     assert(e);
40
41 /*     avahi_log_debug("removing from cache: %p %p", c, e); */
42
43     /* Remove from hash table */
44     t = avahi_hashmap_lookup(c->hashmap, e->record->key);
45     AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e);
46     if (t)
47         avahi_hashmap_replace(c->hashmap, t->record->key, t);
48     else
49         avahi_hashmap_remove(c->hashmap, e->record->key);
50
51     /* Remove from linked list */
52     AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
53
54     if (e->time_event)
55         avahi_time_event_free(e->time_event);
56
57     avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE);
58
59     avahi_record_unref(e->record);
60
61     avahi_free(e);
62
63     assert(c->n_entries >= 1);
64     --c->n_entries;
65 }
66
67 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
68     AvahiCache *c;
69     assert(server);
70
71     if (!(c = avahi_new(AvahiCache, 1))) {
72         avahi_log_error(__FILE__": Out of memory.");
73         return NULL; /* OOM */
74     }
75
76     c->server = server;
77     c->interface = iface;
78
79     if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) {
80         avahi_log_error(__FILE__": Out of memory.");
81         avahi_free(c);
82         return NULL; /* OOM */
83     }
84
85     AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
86     c->n_entries = 0;
87
88     c->last_rand_timestamp = 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_shall_refresh_cache(e->cache->interface, e->record->key))
216             avahi_interface_post_query(e->cache->interface, e->record->key, 0, NULL);
217
218         /* Check again later */
219         next_expiry(e->cache, e, percent);
220
221     }
222
223 /*     avahi_free(txt); */
224 }
225
226 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
227     assert(c);
228     assert(e);
229
230     if (e->time_event)
231         avahi_time_event_update(e->time_event, &e->expiry);
232     else
233         e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
234 }
235
236 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
237     AvahiUsec usec, left, right;
238     time_t now;
239
240     assert(c);
241     assert(e);
242     assert(percent > 0 && percent <= 100);
243
244     usec = (AvahiUsec) e->record->ttl * 10000;
245
246     left = usec * percent;
247     right = usec * (percent+2); /* 2% jitter */
248
249     now = time(NULL);
250
251     if (now >= c->last_rand_timestamp + 10) {
252         c->last_rand = rand();
253         c->last_rand_timestamp = now;
254     }
255
256     usec = left + (AvahiUsec) ((double) (right-left) * c->last_rand / (RAND_MAX+1.0));
257
258     e->expiry = e->timestamp;
259     avahi_timeval_add(&e->expiry, usec);
260
261 /*     g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
262
263     update_time_event(c, e);
264 }
265
266 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
267     assert(c);
268     assert(e);
269
270     e->state = state;
271     gettimeofday(&e->expiry, NULL);
272     avahi_timeval_add(&e->expiry, 1000000); /* 1s */
273     update_time_event(c, e);
274 }
275
276 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
277 /*     char *txt; */
278
279     assert(c);
280     assert(r && r->ref >= 1);
281
282 /*     txt = avahi_record_to_string(r); */
283
284     if (r->ttl == 0) {
285         /* This is a goodbye request */
286
287         AvahiCacheEntry *e;
288
289         if ((e = lookup_record(c, r)))
290             expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
291
292     } else {
293         AvahiCacheEntry *e = NULL, *first;
294         struct timeval now;
295
296         gettimeofday(&now, NULL);
297
298         /* This is an update request */
299
300         if ((first = lookup_key(c, r->key))) {
301
302             if (cache_flush) {
303
304                 /* For unique entries drop all entries older than one second */
305                 for (e = first; e; e = e->by_key_next) {
306                     AvahiUsec t;
307
308                     t = avahi_timeval_diff(&now, &e->timestamp);
309
310                     if (t > 1000000)
311                         expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
312                 }
313             }
314
315             /* Look for exactly the same entry */
316             for (e = first; e; e = e->by_key_next)
317                 if (avahi_record_equal_no_ttl(e->record, r))
318                     break;
319         }
320
321         if (e) {
322
323 /*             avahi_log_debug("found matching cache entry");  */
324
325             /* We need to update the hash table key if we replace the
326              * record */
327             if (e->by_key_prev == NULL)
328                 avahi_hashmap_replace(c->hashmap, r->key, e);
329
330             /* Update the record */
331             avahi_record_unref(e->record);
332             e->record = avahi_record_ref(r);
333
334 /*             avahi_log_debug("cache: updating %s", txt);   */
335
336         } else {
337             /* No entry found, therefore we create a new one */
338
339 /*             avahi_log_debug("cache: couldn't find matching cache entry for %s", txt);   */
340
341             if (c->n_entries >= c->server->config.n_cache_entries_max)
342                 return;
343
344             if (!(e = avahi_new(AvahiCacheEntry, 1))) {
345                 avahi_log_error(__FILE__": Out of memory");
346                 return;
347             }
348
349             e->cache = c;
350             e->time_event = NULL;
351             e->record = avahi_record_ref(r);
352
353             /* Append to hash table */
354             AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
355             avahi_hashmap_replace(c->hashmap, e->record->key, first);
356
357             /* Append to linked list */
358             AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
359
360             c->n_entries++;
361
362             /* Notify subscribers */
363             avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
364         }
365
366         e->origin = *a;
367         e->timestamp = now;
368         next_expiry(c, e, 80);
369         e->state = AVAHI_CACHE_VALID;
370         e->cache_flush = cache_flush;
371     }
372
373 /*     avahi_free(txt);  */
374 }
375
376 struct dump_data {
377     AvahiDumpCallback callback;
378     void* userdata;
379 };
380
381 static void dump_callback(void* key, void* data, void* userdata) {
382     AvahiCacheEntry *e = data;
383     AvahiKey *k = key;
384     struct dump_data *dump_data = userdata;
385
386     assert(k);
387     assert(e);
388     assert(data);
389
390     for (; e; e = e->by_key_next) {
391         char *t;
392
393         if (!(t = avahi_record_to_string(e->record)))
394             continue; /* OOM */
395
396         dump_data->callback(t, dump_data->userdata);
397         avahi_free(t);
398     }
399 }
400
401 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
402     struct dump_data data;
403
404     assert(c);
405     assert(callback);
406
407     callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
408
409     data.callback = callback;
410     data.userdata = userdata;
411
412     avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
413
414     return 0;
415 }
416
417 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
418     struct timeval now;
419     unsigned age;
420
421     assert(c);
422     assert(e);
423
424     gettimeofday(&now, NULL);
425
426     age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
427
428 /*     avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl);  */
429
430     return age >= e->record->ttl/2;
431 }
432
433 void avahi_cache_flush(AvahiCache *c) {
434     assert(c);
435
436     while (c->entries)
437         remove_entry(c, c->entries);
438 }
439
440 /*** Passive observation of failure ***/
441
442 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
443     AvahiAddress *a = userdata;
444     struct timeval now;
445
446     assert(c);
447     assert(pattern);
448     assert(e);
449     assert(a);
450
451     gettimeofday(&now, NULL);
452
453     switch (e->state) {
454         case AVAHI_CACHE_VALID:
455
456             /* The entry was perfectly valid till, now, so let's enter
457              * POOF mode */
458
459             e->state = AVAHI_CACHE_POOF;
460             e->poof_address = *a;
461             e->poof_timestamp = now;
462             e->poof_num = 0;
463
464             break;
465
466         case AVAHI_CACHE_POOF:
467             if (avahi_timeval_diff(&now, &e->poof_timestamp) < 1000000)
468               break;
469
470             e->poof_timestamp = now;
471             e->poof_address = *a;
472             e->poof_num ++;
473
474             /* This is the 4th time we got no response, so let's
475              * fucking remove this entry. */
476             if (e->poof_num > 3)
477               expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
478             break;
479
480         default:
481             ;
482     }
483
484     return NULL;
485 }
486
487 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
488     assert(c);
489     assert(key);
490
491     avahi_cache_walk(c, key, start_poof_callback, (void*) a);
492 }
493
494 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
495     AvahiCacheEntry *e;
496
497     assert(c);
498     assert(record);
499     assert(a);
500
501     if (!(e = lookup_record(c, record)))
502         return;
503
504     /* This function is called for each response suppression
505        record. If the matching cache entry is in POOF state and the
506        query address is the same, we put it back into valid mode */
507
508     if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
509         if (avahi_address_cmp(a, &e->poof_address) == 0) {
510             e->state = AVAHI_CACHE_VALID;
511             next_expiry(c, e, 80);
512         }
513 }