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/avahi-malloc.h"
30
31#include "cache.h"
32#include "log.h"
33#include "rr-util.h"
34
35static 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
67AvahiCache *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
93void 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
105static 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
114void* 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
146static 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
157static 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
164static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
165
166static 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
226static 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
236static 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
266static 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
276void 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
376struct dump_data {
377    AvahiDumpCallback callback;
378    void* userdata;
379};
380
381static 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
401int 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
417int 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
433void 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
442static 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
487void 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
494void 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}
514