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