git.meshlink.io Git - catta/blob - 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
  35 #define AVAHI_MAX_CACHE_ENTRIES 500
  36
  37 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
  38     AvahiCacheEntry *t;
  39
  40     assert(c);
  41     assert(e);
  42
  43 /*     avahi_log_debug("removing from cache: %p %p", c, e); */
  44
  45     /* Remove from hash table */
  46     t = avahi_hashmap_lookup(c->hashmap, e->record->key);
  47     AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e);
  48     if (t)
  49         avahi_hashmap_replace(c->hashmap, t->record->key, t);
  50     else
  51         avahi_hashmap_remove(c->hashmap, e->record->key);
  52
  53     /* Remove from linked list */
  54     AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
  55
  56     if (e->time_event)
  57         avahi_time_event_free(e->time_event);
  58
  59     avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE);
  60
  61     avahi_record_unref(e->record);
  62
  63     avahi_free(e);
  64
  65     assert(c->n_entries-- >= 1);
  66 }
  67
  68 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
  69     AvahiCache *c;
  70     assert(server);
  71
  72     if (!(c = avahi_new(AvahiCache, 1))) {
  73         avahi_log_error(__FILE__": Out of memory.");
  74         return NULL; /* OOM */
  75     }
  76
  77     c->server = server;
  78     c->interface = iface;
  79
  80     if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) {
  81         avahi_log_error(__FILE__": Out of memory.");
  82         avahi_free(c);
  83         return NULL; /* OOM */
  84     }
  85
  86     AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
  87     c->n_entries = 0;
  88
  89     return c;
  90 }
  91
  92 void avahi_cache_free(AvahiCache *c) {
  93     assert(c);
  94
  95     while (c->entries)
  96         remove_entry(c, c->entries);
  97     assert(c->n_entries == 0);
  98
  99     avahi_hashmap_free(c->hashmap);
 100
 101     avahi_free(c);
 102 }
 103
 104 AvahiCacheEntry *avahi_cache_lookup_key(AvahiCache *c, AvahiKey *k) {
 105     assert(c);
 106     assert(k);
 107
 108     assert(!avahi_key_is_pattern(k));
 109
 110     return avahi_hashmap_lookup(c->hashmap, k);
 111 }
 112
 113 void* avahi_cache_walk(AvahiCache *c, AvahiKey *pattern, AvahiCacheWalkCallback cb, void* userdata) {
 114     void* ret;
 115
 116     assert(c);
 117     assert(pattern);
 118     assert(cb);
 119
 120     if (avahi_key_is_pattern(pattern)) {
 121         AvahiCacheEntry *e, *n;
 122
 123         for (e = c->entries; e; e = n) {
 124             n = e->entry_next;
 125
 126             if (avahi_key_pattern_match(pattern, e->record->key))
 127                 if ((ret = cb(c, pattern, e, userdata)))
 128                     return ret;
 129         }
 130
 131     } else {
 132         AvahiCacheEntry *e, *n;
 133
 134         for (e = avahi_cache_lookup_key(c, pattern); e; e = n) {
 135             n = e->by_key_next;
 136
 137             if ((ret = cb(c, pattern, e, userdata)))
 138                 return ret;
 139         }
 140     }
 141
 142     return NULL;
 143 }
 144
 145 static void* lookup_record_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
 146     assert(c);
 147     assert(pattern);
 148     assert(e);
 149
 150     if (avahi_record_equal_no_ttl(e->record, userdata))
 151         return e;
 152
 153     return NULL;
 154 }
 155
 156 AvahiCacheEntry *avahi_cache_lookup_record(AvahiCache *c, AvahiRecord *r) {
 157     assert(c);
 158     assert(r);
 159
 160     return avahi_cache_walk(c, r->key, lookup_record_callback, r);
 161 }
 162
 163 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent);
 164
 165 static void elapse_func(AvahiTimeEvent *t, void *userdata) {
 166     AvahiCacheEntry *e = userdata;
 167 /*     char *txt; */
 168
 169     assert(t);
 170     assert(e);
 171
 172 /*     txt = avahi_record_to_string(e->record); */
 173
 174     if (e->state == AVAHI_CACHE_FINAL) {
 175         remove_entry(e->cache, e);
 176 /*         avahi_log_debug("Removing entry from cache due to expiration (%s)", txt); */
 177     } else {
 178         unsigned percent = 0;
 179
 180         switch (e->state) {
 181             case AVAHI_CACHE_VALID:
 182                 e->state = AVAHI_CACHE_EXPIRY1;
 183                 percent = 85;
 184                 break;
 185
 186             case AVAHI_CACHE_EXPIRY1:
 187                 e->state = AVAHI_CACHE_EXPIRY2;
 188                 percent = 90;
 189                 break;
 190             case AVAHI_CACHE_EXPIRY2:
 191                 e->state = AVAHI_CACHE_EXPIRY3;
 192                 percent = 95;
 193                 break;
 194
 195             case AVAHI_CACHE_EXPIRY3:
 196                 e->state = AVAHI_CACHE_FINAL;
 197                 percent = 100;
 198                 break;
 199
 200             default:
 201                 ;
 202         }
 203
 204         assert(percent > 0);
 205
 206         /* Request a cache update, if we are subscribed to this entry */
 207         if (avahi_querier_exists(e->cache->interface, e->record->key)) {
 208 /*             avahi_log_debug("Requesting cache entry update at %i%% for %s.", percent, txt);   */
 209             avahi_interface_post_query(e->cache->interface, e->record->key, 1);
 210         }
 211
 212         /* Check again later */
 213         next_expiry(e->cache, e, percent);
 214     }
 215
 216 /*     avahi_free(txt); */
 217 }
 218
 219 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
 220     assert(c);
 221     assert(e);
 222
 223     if (e->time_event)
 224         avahi_time_event_update(e->time_event, &e->expiry);
 225     else
 226         e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
 227 }
 228
 229 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
 230     AvahiUsec usec, left, right;
 231
 232     assert(c);
 233     assert(e);
 234     assert(percent > 0 && percent <= 100);
 235
 236     usec = (AvahiUsec) e->record->ttl * 10000;
 237
 238     left = usec * percent;
 239     right = usec * (percent+2); /* 2% jitter */
 240
 241     usec = left + (AvahiUsec) ((double) (right-left) * rand() / (RAND_MAX+1.0));
 242
 243     e->expiry = e->timestamp;
 244     avahi_timeval_add(&e->expiry, usec);
 245
 246 /*     g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
 247
 248     update_time_event(c, e);
 249 }
 250
 251 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e) {
 252     assert(c);
 253     assert(e);
 254
 255     e->state = AVAHI_CACHE_FINAL;
 256     gettimeofday(&e->expiry, NULL);
 257     avahi_timeval_add(&e->expiry, 1000000); /* 1s */
 258     update_time_event(c, e);
 259 }
 260
 261 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
 262 /*     char *txt; */
 263
 264     assert(c);
 265     assert(r && r->ref >= 1);
 266
 267 /*     txt = avahi_record_to_string(r); */
 268
 269     if (r->ttl == 0) {
 270         /* This is a goodbye request */
 271
 272         AvahiCacheEntry *e;
 273
 274         if ((e = avahi_cache_lookup_record(c, r)))
 275             expire_in_one_second(c, e);
 276
 277     } else {
 278         AvahiCacheEntry *e = NULL, *first;
 279         struct timeval now;
 280
 281         gettimeofday(&now, NULL);
 282
 283         /* This is an update request */
 284
 285         if ((first = avahi_cache_lookup_key(c, r->key))) {
 286
 287             if (cache_flush) {
 288
 289                 /* For unique entries drop all entries older than one second */
 290                 for (e = first; e; e = e->by_key_next) {
 291                     AvahiUsec t;
 292
 293                     t = avahi_timeval_diff(&now, &e->timestamp);
 294
 295                     if (t > 1000000)
 296                         expire_in_one_second(c, e);
 297                 }
 298             }
 299
 300             /* Look for exactly the same entry */
 301             for (e = first; e; e = e->by_key_next)
 302                 if (avahi_record_equal_no_ttl(e->record, r))
 303                     break;
 304         }
 305
 306         if (e) {
 307
 308 /*             avahi_log_debug("found matching cache entry");  */
 309
 310             /* We need to update the hash table key if we replace the
 311              * record */
 312             if (e->by_key_prev == NULL)
 313                 avahi_hashmap_replace(c->hashmap, r->key, e);
 314
 315             /* Update the record */
 316             avahi_record_unref(e->record);
 317             e->record = avahi_record_ref(r);
 318
 319 /*             avahi_log_debug("cache: updating %s", txt);   */
 320
 321         } else {
 322             /* No entry found, therefore we create a new one */
 323
 324 /*             avahi_log_debug("cache: couldn't find matching cache entry for %s", txt);   */
 325
 326             if (c->n_entries >= AVAHI_MAX_CACHE_ENTRIES)
 327                 return;
 328
 329             if (!(e = avahi_new(AvahiCacheEntry, 1))) {
 330                 avahi_log_error(__FILE__": Out of memory");
 331                 return;
 332             }
 333
 334             e->cache = c;
 335             e->time_event = NULL;
 336             e->record = avahi_record_ref(r);
 337
 338             /* Append to hash table */
 339             AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
 340             avahi_hashmap_replace(c->hashmap, e->record->key, first);
 341
 342             /* Append to linked list */
 343             AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
 344
 345             c->n_entries++;
 346
 347             /* Notify subscribers */
 348             avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
 349         }
 350
 351         e->origin = *a;
 352         e->timestamp = now;
 353         next_expiry(c, e, 80);
 354         e->state = AVAHI_CACHE_VALID;
 355         e->cache_flush = cache_flush;
 356     }
 357
 358 /*     avahi_free(txt);  */
 359 }
 360
 361 struct dump_data {
 362     AvahiDumpCallback callback;
 363     void* userdata;
 364 };
 365
 366 static void dump_callback(void* key, void* data, void* userdata) {
 367     AvahiCacheEntry *e = data;
 368     AvahiKey *k = key;
 369     struct dump_data *dump_data = userdata;
 370
 371     assert(k);
 372     assert(e);
 373     assert(data);
 374
 375     for (; e; e = e->by_key_next) {
 376         char *t;
 377
 378         if (!(t = avahi_record_to_string(e->record)))
 379             continue; /* OOM */
 380
 381         dump_data->callback(t, dump_data->userdata);
 382         avahi_free(t);
 383     }
 384 }
 385
 386 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
 387     struct dump_data data;
 388
 389     assert(c);
 390     assert(callback);
 391
 392     callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
 393
 394     data.callback = callback;
 395     data.userdata = userdata;
 396
 397     avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
 398
 399     return 0;
 400 }
 401
 402 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
 403     struct timeval now;
 404     unsigned age;
 405
 406     assert(c);
 407     assert(e);
 408
 409     gettimeofday(&now, NULL);
 410
 411     age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
 412
 413 /*     avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl);  */
 414
 415     return age >= e->record->ttl/2;
 416 }
 417
 418 void avahi_cache_flush(AvahiCache *c) {
 419     assert(c);
 420
 421     while (c->entries)
 422         remove_entry(c, c->entries);
 423 }