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