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 static void remove_entry(AvahiCache *c, AvahiCacheEntry *e) {
  36     AvahiCacheEntry *t;
  37
  38     assert(c);
  39     assert(e);
  40
  41 /*     avahi_log_debug("removing from cache: %p %p", c, e); */
  42
  43     /* Remove from hash table */
  44     t = avahi_hashmap_lookup(c->hashmap, e->record->key);
  45     AVAHI_LLIST_REMOVE(AvahiCacheEntry, by_key, t, e);
  46     if (t)
  47         avahi_hashmap_replace(c->hashmap, t->record->key, t);
  48     else
  49         avahi_hashmap_remove(c->hashmap, e->record->key);
  50
  51     /* Remove from linked list */
  52     AVAHI_LLIST_REMOVE(AvahiCacheEntry, entry, c->entries, e);
  53
  54     if (e->time_event)
  55         avahi_time_event_free(e->time_event);
  56
  57     avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_REMOVE);
  58
  59     avahi_record_unref(e->record);
  60
  61     avahi_free(e);
  62
  63     assert(c->n_entries >= 1);
  64     --c->n_entries;
  65 }
  66
  67 AvahiCache *avahi_cache_new(AvahiServer *server, AvahiInterface *iface) {
  68     AvahiCache *c;
  69     assert(server);
  70
  71     if (!(c = avahi_new(AvahiCache, 1))) {
  72         avahi_log_error(__FILE__": Out of memory.");
  73         return NULL; /* OOM */
  74     }
  75
  76     c->server = server;
  77     c->interface = iface;
  78
  79     if (!(c->hashmap = avahi_hashmap_new((AvahiHashFunc) avahi_key_hash, (AvahiEqualFunc) avahi_key_equal, NULL, NULL))) {
  80         avahi_log_error(__FILE__": Out of memory.");
  81         avahi_free(c);
  82         return NULL; /* OOM */
  83     }
  84
  85     AVAHI_LLIST_HEAD_INIT(AvahiCacheEntry, c->entries);
  86     c->n_entries = 0;
  87
  88     c->last_rand_timestamp = 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_shall_refresh_cache(e->cache->interface, e->record->key))
 216             avahi_interface_post_query(e->cache->interface, e->record->key, 0, NULL);
 217
 218         /* Check again later */
 219         next_expiry(e->cache, e, percent);
 220
 221     }
 222
 223 /*     avahi_free(txt); */
 224 }
 225
 226 static void update_time_event(AvahiCache *c, AvahiCacheEntry *e) {
 227     assert(c);
 228     assert(e);
 229
 230     if (e->time_event)
 231         avahi_time_event_update(e->time_event, &e->expiry);
 232     else
 233         e->time_event = avahi_time_event_new(c->server->time_event_queue, &e->expiry, elapse_func, e);
 234 }
 235
 236 static void next_expiry(AvahiCache *c, AvahiCacheEntry *e, unsigned percent) {
 237     AvahiUsec usec, left, right;
 238     time_t now;
 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     now = time(NULL);
 250
 251     if (now >= c->last_rand_timestamp + 10) {
 252         c->last_rand = rand();
 253         c->last_rand_timestamp = now;
 254     }
 255
 256     usec = left + (AvahiUsec) ((double) (right-left) * c->last_rand / (RAND_MAX+1.0));
 257
 258     e->expiry = e->timestamp;
 259     avahi_timeval_add(&e->expiry, usec);
 260
 261 /*     g_message("wake up in +%lu seconds", e->expiry.tv_sec - e->timestamp.tv_sec); */
 262
 263     update_time_event(c, e);
 264 }
 265
 266 static void expire_in_one_second(AvahiCache *c, AvahiCacheEntry *e, AvahiCacheEntryState state) {
 267     assert(c);
 268     assert(e);
 269
 270     e->state = state;
 271     gettimeofday(&e->expiry, NULL);
 272     avahi_timeval_add(&e->expiry, 1000000); /* 1s */
 273     update_time_event(c, e);
 274 }
 275
 276 void avahi_cache_update(AvahiCache *c, AvahiRecord *r, int cache_flush, const AvahiAddress *a) {
 277 /*     char *txt; */
 278
 279     assert(c);
 280     assert(r && r->ref >= 1);
 281
 282 /*     txt = avahi_record_to_string(r); */
 283
 284     if (r->ttl == 0) {
 285         /* This is a goodbye request */
 286
 287         AvahiCacheEntry *e;
 288
 289         if ((e = lookup_record(c, r)))
 290             expire_in_one_second(c, e, AVAHI_CACHE_GOODBYE_FINAL);
 291
 292     } else {
 293         AvahiCacheEntry *e = NULL, *first;
 294         struct timeval now;
 295
 296         gettimeofday(&now, NULL);
 297
 298         /* This is an update request */
 299
 300         if ((first = lookup_key(c, r->key))) {
 301
 302             if (cache_flush) {
 303
 304                 /* For unique entries drop all entries older than one second */
 305                 for (e = first; e; e = e->by_key_next) {
 306                     AvahiUsec t;
 307
 308                     t = avahi_timeval_diff(&now, &e->timestamp);
 309
 310                     if (t > 1000000)
 311                         expire_in_one_second(c, e, AVAHI_CACHE_REPLACE_FINAL);
 312                 }
 313             }
 314
 315             /* Look for exactly the same entry */
 316             for (e = first; e; e = e->by_key_next)
 317                 if (avahi_record_equal_no_ttl(e->record, r))
 318                     break;
 319         }
 320
 321         if (e) {
 322
 323 /*             avahi_log_debug("found matching cache entry");  */
 324
 325             /* We need to update the hash table key if we replace the
 326              * record */
 327             if (e->by_key_prev == NULL)
 328                 avahi_hashmap_replace(c->hashmap, r->key, e);
 329
 330             /* Update the record */
 331             avahi_record_unref(e->record);
 332             e->record = avahi_record_ref(r);
 333
 334 /*             avahi_log_debug("cache: updating %s", txt);   */
 335
 336         } else {
 337             /* No entry found, therefore we create a new one */
 338
 339 /*             avahi_log_debug("cache: couldn't find matching cache entry for %s", txt);   */
 340
 341             if (c->n_entries >= c->server->config.n_cache_entries_max)
 342                 return;
 343
 344             if (!(e = avahi_new(AvahiCacheEntry, 1))) {
 345                 avahi_log_error(__FILE__": Out of memory");
 346                 return;
 347             }
 348
 349             e->cache = c;
 350             e->time_event = NULL;
 351             e->record = avahi_record_ref(r);
 352
 353             /* Append to hash table */
 354             AVAHI_LLIST_PREPEND(AvahiCacheEntry, by_key, first, e);
 355             avahi_hashmap_replace(c->hashmap, e->record->key, first);
 356
 357             /* Append to linked list */
 358             AVAHI_LLIST_PREPEND(AvahiCacheEntry, entry, c->entries, e);
 359
 360             c->n_entries++;
 361
 362             /* Notify subscribers */
 363             avahi_multicast_lookup_engine_notify(c->server->multicast_lookup_engine, c->interface, e->record, AVAHI_BROWSER_NEW);
 364         }
 365
 366         e->origin = *a;
 367         e->timestamp = now;
 368         next_expiry(c, e, 80);
 369         e->state = AVAHI_CACHE_VALID;
 370         e->cache_flush = cache_flush;
 371     }
 372
 373 /*     avahi_free(txt);  */
 374 }
 375
 376 struct dump_data {
 377     AvahiDumpCallback callback;
 378     void* userdata;
 379 };
 380
 381 static void dump_callback(void* key, void* data, void* userdata) {
 382     AvahiCacheEntry *e = data;
 383     AvahiKey *k = key;
 384     struct dump_data *dump_data = userdata;
 385
 386     assert(k);
 387     assert(e);
 388     assert(data);
 389
 390     for (; e; e = e->by_key_next) {
 391         char *t;
 392
 393         if (!(t = avahi_record_to_string(e->record)))
 394             continue; /* OOM */
 395
 396         dump_data->callback(t, dump_data->userdata);
 397         avahi_free(t);
 398     }
 399 }
 400
 401 int avahi_cache_dump(AvahiCache *c, AvahiDumpCallback callback, void* userdata) {
 402     struct dump_data data;
 403
 404     assert(c);
 405     assert(callback);
 406
 407     callback(";;; CACHE DUMP FOLLOWS ;;;", userdata);
 408
 409     data.callback = callback;
 410     data.userdata = userdata;
 411
 412     avahi_hashmap_foreach(c->hashmap, dump_callback, &data);
 413
 414     return 0;
 415 }
 416
 417 int avahi_cache_entry_half_ttl(AvahiCache *c, AvahiCacheEntry *e) {
 418     struct timeval now;
 419     unsigned age;
 420
 421     assert(c);
 422     assert(e);
 423
 424     gettimeofday(&now, NULL);
 425
 426     age = (unsigned) (avahi_timeval_diff(&now, &e->timestamp)/1000000);
 427
 428 /*     avahi_log_debug("age: %lli, ttl/2: %u", age, e->record->ttl);  */
 429
 430     return age >= e->record->ttl/2;
 431 }
 432
 433 void avahi_cache_flush(AvahiCache *c) {
 434     assert(c);
 435
 436     while (c->entries)
 437         remove_entry(c, c->entries);
 438 }
 439
 440 /*** Passive observation of failure ***/
 441
 442 static void* start_poof_callback(AvahiCache *c, AvahiKey *pattern, AvahiCacheEntry *e, void *userdata) {
 443     AvahiAddress *a = userdata;
 444     struct timeval now;
 445
 446     assert(c);
 447     assert(pattern);
 448     assert(e);
 449     assert(a);
 450
 451     gettimeofday(&now, NULL);
 452
 453     switch (e->state) {
 454         case AVAHI_CACHE_VALID:
 455
 456             /* The entry was perfectly valid till, now, so let's enter
 457              * POOF mode */
 458
 459             e->state = AVAHI_CACHE_POOF;
 460             e->poof_address = *a;
 461             e->poof_timestamp = now;
 462             e->poof_num = 0;
 463
 464             break;
 465
 466         case AVAHI_CACHE_POOF:
 467             if (avahi_timeval_diff(&now, &e->poof_timestamp) < 1000000)
 468               break;
 469
 470             e->poof_timestamp = now;
 471             e->poof_address = *a;
 472             e->poof_num ++;
 473
 474             /* This is the 4th time we got no response, so let's
 475              * fucking remove this entry. */
 476             if (e->poof_num > 3)
 477               expire_in_one_second(c, e, AVAHI_CACHE_POOF_FINAL);
 478             break;
 479
 480         default:
 481             ;
 482     }
 483
 484     return NULL;
 485 }
 486
 487 void avahi_cache_start_poof(AvahiCache *c, AvahiKey *key, const AvahiAddress *a) {
 488     assert(c);
 489     assert(key);
 490
 491     avahi_cache_walk(c, key, start_poof_callback, (void*) a);
 492 }
 493
 494 void avahi_cache_stop_poof(AvahiCache *c, AvahiRecord *record, const AvahiAddress *a) {
 495     AvahiCacheEntry *e;
 496
 497     assert(c);
 498     assert(record);
 499     assert(a);
 500
 501     if (!(e = lookup_record(c, record)))
 502         return;
 503
 504     /* This function is called for each response suppression
 505        record. If the matching cache entry is in POOF state and the
 506        query address is the same, we put it back into valid mode */
 507
 508     if (e->state == AVAHI_CACHE_POOF || e->state == AVAHI_CACHE_POOF_FINAL)
 509         if (avahi_address_cmp(a, &e->poof_address) == 0) {
 510             e->state = AVAHI_CACHE_VALID;
 511             next_expiry(c, e, 80);
 512         }
 513 }