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