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