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 #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_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
 239     assert(c);
 240     assert(e);
 241     assert(percent > 0 && percent <= 100);
 242
 243     usec = (AvahiUsec) e->record->ttl * 10000;
 244
 245     left = usec * percent;
 246     right = usec * (percent+2); /* 2% jitter */
 247
 248     usec = left + (AvahiUsec) ((double) (right-left) * rand() / (RAND_MAX+1.0));
 249
 250     e->expiry = e->timestamp;
 251     avahi_timeval_add(&e->expiry, usec);
 252
 253 /*     g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
 254
 255     update_time_event(c, e);
 256 }
 257
 258 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
 259     assert(c);
 260     assert(e);
 261
 262     e->state = state;
 263     gettimeofday(&e->expiry, NULL);
 264     avahi_timeval_add(&e->expiry, 1000000); /* 1s */
 265     update_time_event(c, e);
 266 }
 267
 268 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
 269 /*     char *txt; */
 270
 271     assert(c);
 272     assert(r && r->ref >= 1);
 273
 274 /*     txt = avahi_record_to_string(r); */
 275
 276     if (r->ttl == 0) {
 277         /* This is a goodbye request */
 278
 279         AvahiCacheEntry *e;
 280
 281         if ((e = lookup_record(c, r)))
 282             expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
 283
 284     } else {
 285         AvahiCacheEntry *e = NULL, *first;
 286         struct timeval now;
 287
 288         gettimeofday(&now, NULL);
 289
 290         /* This is an update request */
 291
 292         if ((first = lookup_key(c, r->key))) {
 293
 294             if (cache_flush) {
 295
 296                 /* For unique entries drop all entries older than one second */
 297                 for (e = first; e; e = e->by_key_next) {
 298                     AvahiUsec t;
 299
 300                     t = avahi_timeval_diff(&now, &e->timestamp);
 301
 302                     if (t > 1000000)
 303                         expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
 304                 }
 305             }
 306
 307             /* Look for exactly the same entry */
 308             for (e = first; e; e = e->by_key_next)
 309                 if (avahi_record_equal_no_ttl(e->record, r))
 310                     break;
 311         }
 312
 313         if (e) {
 314
 315 /*             avahi_log_debug("found matching cache entry");  */
 316
 317             /* We need to update the hash table key if we replace the
 318              * record */
 319             if (e->by_key_prev == NULL)
 320                 avahi_hashmap_replace(c->hashmap, r->key, e);
 321
 322             /* Update the record */
 323             avahi_record_unref(e->record);
 324             e->record = avahi_record_ref(r);
 325
 326 /*             avahi_log_debug("cache: updating %s", txt);   */
 327
 328         } else {
 329             /* No entry found, therefore we create a new one */
 330
 331 /*             avahi_log_debug("cache: couldn't find matching cache entry for %s", txt);   */
 332
 333             if (c->n_entries >= AVAHI_CACHE_ENTRIES_MAX)
 334                 return;
 335
 336             if (!(e = avahi_new(AvahiCacheEntry, 1))) {
 337                 avahi_log_error(__FILE__": Out of memory");
 338                 return;
 339             }
 340
 341             e->cache = c;
 342             e->time_event = NULL;
 343             e->record = avahi_record_ref(r);
 344
 345             /* Append to hash table */
 346             AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
 347             avahi_hashmap_replace(c->hashmap, e->record->key, first);
 348
 349             /* Append to linked list */
 350             AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
 351
 352             c->n_entries++;
 353
 354             /* Notify subscribers */
 355             avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
 356         }
 357
 358         e->origin = *a;
 359         e->timestamp = now;
 360         next_expiry(c, e, 80);
 361         e->state = AVAHI_CACHE_VALID;
 362         e->cache_flush = cache_flush;
 363     }
 364
 365 /*     avahi_free(txt);  */
 366 }
 367
 368 struct dump_data {
 369     AvahiDumpCallback callback;
 370     void* userdata;
 371 };
 372
 373 static void dump_callback(void* key, void* data, void* userdata) {
 374     AvahiCacheEntry *e = data;
 375     AvahiKey *k = key;
 376     struct dump_data *dump_data = userdata;
 377
 378     assert(k);
 379     assert(e);
 380     assert(data);
 381
 382     for (; e; e = e->by_key_next) {
 383         char *t;
 384
 385         if (!(t = avahi_record_to_string(e->record)))
 386             continue; /* OOM */
 387
 388         dump_data->callback(t, dump_data->userdata);
 389         avahi_free(t);
 390     }
 391 }
 392
 393 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
 394     struct dump_data data;
 395
 396     assert(c);
 397     assert(callback);
 398
 399     callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
 400
 401     data.callback = callback;
 402     data.userdata = userdata;
 403
 404     avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
 405
 406     return 0;
 407 }
 408
 409 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
 410     struct timeval now;
 411     unsigned age;
 412
 413     assert(c);
 414     assert(e);
 415
 416     gettimeofday(&now, NULL);
 417
 418     age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
 419
 420 /*     avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl);  */
 421
 422     return age >= e->record->ttl/2;
 423 }
 424
 425 void avahi_cache_flush(AvahiCache *c) {
 426     assert(c);
 427
 428     while (c->entries)
 429         remove_entry(c, c->entries);
 430 }
 431
 432 /*** Passive observation of failure ***/
 433
 434 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
 435     AvahiAddress *a = userdata;
 436
 437     assert(c);
 438     assert(pattern);
 439     assert(e);
 440     assert(a);
 441
 442     switch (e->state) {
 443         case AVAHI_CACHE_VALID:
 444
 445             /* The entry was perfectly valid till, now, so let's enter
 446              * POOF mode */
 447
 448             e->state = AVAHI_CACHE_POOF;
 449             e->poof_address = *a;
 450
 451             break;
 452
 453         case AVAHI_CACHE_POOF:
 454
 455             /* This is the second time we got no response, so let's
 456              * fucking remove this entry. */
 457
 458             expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
 459             break;
 460
 461         default:
 462             ;
 463     }
 464
 465     return NULL;
 466 }
 467
 468 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
 469     assert(c);
 470     assert(key);
 471
 472     avahi_cache_walk(c, key, start_poof_callback, a);
 473 }
 474
 475 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
 476     AvahiCacheEntry *e;
 477
 478     assert(c);
 479     assert(record);
 480     assert(a);
 481
 482     if (!(e = lookup_record(c, record)))
 483         return;
 484
 485     /* This function is called for each response suppression
 486        record. If the matching cache entry is in POOF state and the
 487        query address is the same, we put it back into valid mode */
 488
 489     if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
 490         if (avahi_address_cmp(a, &e->poof_address) == 0) {
 491             e->state = AVAHI_CACHE_VALID;
 492             next_expiry(c, e, 80);
 493         }
 494 }
 495
 496
 497