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