git.meshlink.io Git - catta/blob - avahi-core/cache.c

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