X-Git-Url: http://git.meshlink.io/?a=blobdiff_plain;ds=sidebyside;f=cache.c;h=bbf667b43c5264b66940080634a2d660a02c8372;hb=cfc653d0fd2f58ef3f4b5ecb285d5beb5bfaacfb;hp=6a0a874da433fdb4ff43ad962606356141f743fe;hpb=0781d5363fb6fd723a2316fc7558aef6439b2f71;p=catta

diff --git a/cache.c b/cache.c
index 6a0a874..bbf667b 100644
--- a/cache.c
+++ b/cache.c
@@ -1,22 +1,34 @@
 #include <string.h>
 
+#include "util.h"
 #include "cache.h"
 
-static void remove_entry(flxCache *c, flxCacheEntry *e, gboolean remove_from_hash_table) {
+static void remove_entry(flxCache *c, flxCacheEntry *e) {
+    flxCacheEntry *t;
+
     g_assert(c);
     g_assert(e);
 
-    if (remove_from_hash_table) {
-        flxCacheEntry *t;
-        t = g_hash_table_lookup(c->hash_table, &e->record->key);
-        FLX_LLIST_REMOVE(flxCacheEntry, by_name, t, e);
-        if (t)
-            g_hash_table_replace(c->hash_table, &t->record->key, t);
-        else
-            g_hash_table_remove(c->hash_table, &e->record->key);
-    }
+/*     g_message("removing from cache: %p %p", c, e); */
+
+    /* Remove from hash table */
+    t = g_hash_table_lookup(c->hash_table, e->record->key);
+    FLX_LLIST_REMOVE(flxCacheEntry, by_key, t, e);
+    if (t)
+        g_hash_table_replace(c->hash_table, t->record->key, t);
+    else
+        g_hash_table_remove(c->hash_table, e->record->key);
+
+    /* Remove from linked list */
+    FLX_LLIST_REMOVE(flxCacheEntry, entry, c->entries, e);
         
+    if (e->time_event)
+        flx_time_event_queue_remove(c->server->time_event_queue, e->time_event);
+
+    flx_subscription_notify(c->server, c->interface, e->record, FLX_SUBSCRIPTION_REMOVE);
+
     flx_record_unref(e->record);
+    
     g_free(e);
 }
 
@@ -29,24 +41,17 @@ flxCache *flx_cache_new(flxServer *server, flxInterface *iface) {
     c->interface = iface;
     c->hash_table = g_hash_table_new((GHashFunc) flx_key_hash, (GEqualFunc) flx_key_equal);
 
-    return c;
-}
-
-gboolean remove_func(gpointer key, gpointer value, gpointer user_data) {
-    flxCacheEntry *e, *next;
-
-    for (e = value; e; e = next) {
-        next = e->by_name_next;
-        remove_entry(user_data, e, FALSE);
-    }
+    FLX_LLIST_HEAD_INIT(flxCacheEntry, c->entries);
     
-    return TRUE;
+    return c;
 }
 
 void flx_cache_free(flxCache *c) {
     g_assert(c);
 
-    g_hash_table_foreach_remove(c->hash_table, remove_func, c);
+    while (c->entries)
+        remove_entry(c, c->entries);
+    
     g_hash_table_destroy(c->hash_table);
     
     g_free(c);
@@ -56,86 +61,244 @@ flxCacheEntry *flx_cache_lookup_key(flxCache *c, flxKey *k) {
     g_assert(c);
     g_assert(k);
 
+    g_assert(!flx_key_is_pattern(k));
+    
     return g_hash_table_lookup(c->hash_table, k);
 }
 
+gpointer flx_cache_walk(flxCache *c, flxKey *pattern, flxCacheWalkCallback cb, gpointer userdata) {
+    gpointer ret;
+    
+    g_assert(c);
+    g_assert(pattern);
+    g_assert(cb);
+    
+    if (flx_key_is_pattern(pattern)) {
+        flxCacheEntry *e, *n;
+        
+        for (e = c->entries; e; e = n) {
+            n = e->entry_next;
+            
+            if (flx_key_pattern_match(pattern, e->record->key))
+                if ((ret = cb(c, pattern, e, userdata)))
+                    return ret;
+        }
+        
+    } else {
+        flxCacheEntry *e, *n;
+
+        for (e = flx_cache_lookup_key(c, pattern); e; e = n) {
+            n = e->by_key_next;
+                
+            if ((ret = cb(c, pattern, e, userdata)))
+                return ret;
+        }
+    }
+
+    return NULL;
+}
+
+static gpointer lookup_record_callback(flxCache *c, flxKey *pattern, flxCacheEntry *e, void *userdata) {
+    g_assert(c);
+    g_assert(pattern);
+    g_assert(e);
+
+    if (flx_record_equal_no_ttl(e->record, userdata))
+        return e;
+
+    return NULL;
+}
+
 flxCacheEntry *flx_cache_lookup_record(flxCache *c, flxRecord *r) {
     flxCacheEntry *e;
+    
     g_assert(c);
     g_assert(r);
 
-    for (e = flx_cache_lookup_key(c, r->key); e; e = e->by_name_next)
-        if (e->record->size == r->size && !memcmp(e->record->data, r->data, r->size))
-            return e;
+    return flx_cache_walk(c, r->key, lookup_record_callback, r);
+}
 
-    return NULL;
+static void next_expiry(flxCache *c, flxCacheEntry *e, guint percent);
+
+static void elapse_func(flxTimeEvent *t, void *userdata) {
+    flxCacheEntry *e = userdata;
+    
+    g_assert(t);
+    g_assert(e);
+
+    if (e->state == FLX_CACHE_FINAL) {
+        remove_entry(e->cache, e);
+        g_message("Removing entry from cache due to expiration");
+    } else {
+        guint percent = 0;
+    
+        switch (e->state) {
+            case FLX_CACHE_VALID:
+                e->state = FLX_CACHE_EXPIRY1;
+                percent = 85;
+                break;
+                
+            case FLX_CACHE_EXPIRY1:
+                e->state = FLX_CACHE_EXPIRY2;
+                percent = 90;
+                break;
+            case FLX_CACHE_EXPIRY2:
+                e->state = FLX_CACHE_EXPIRY3;
+                percent = 95;
+                break;
+                
+            case FLX_CACHE_EXPIRY3:
+                e->state = FLX_CACHE_FINAL;
+                percent = 100;
+                break;
+
+            default:
+                ;
+        }
+
+        g_assert(percent > 0);
+
+        g_message("Requesting cache entry update at %i%%.", percent);
+
+        /* Request a cache update, if we are subscribed to this entry */
+        if (flx_is_subscribed(e->cache->server, e->record->key))
+            flx_interface_post_query(e->cache->interface, e->record->key, TRUE);
+
+        /* Check again later */
+        next_expiry(e->cache, e, percent);
+    }
 }
 
-flxCacheEntry *flx_cache_update(flxCache *c, flxRecord *r, gboolean unique, const flxAddress *a) {
-    flxCacheEntry *e, *t;
+static void update_time_event(flxCache *c, flxCacheEntry *e) {
+    g_assert(c);
+    g_assert(e);
     
+    if (e->time_event)
+        flx_time_event_queue_update(c->server->time_event_queue, e->time_event, &e->expiry);
+    else
+        e->time_event = flx_time_event_queue_add(c->server->time_event_queue, &e->expiry, elapse_func, e);
+}
+
+static void next_expiry(flxCache *c, flxCacheEntry *e, guint percent) {
+    gulong usec;
+
     g_assert(c);
-    g_assert(r);
+    g_assert(e);
+    g_assert(percent > 0 && percent <= 100);
+
+    e->expiry = e->timestamp;
 
-    if ((t = e = flx_cache_lookup_key(c, r->key))) {
+    usec = e->record->ttl * 10000;
+
+    /* 2% jitter */
+    usec = g_random_int_range(usec*percent, usec*(percent+2));
+    
+    g_time_val_add(&e->expiry, usec);
+    update_time_event(c, e);
+}
 
-        if (unique) {
-            flxCacheEntry *n;
-            /* Drop all entries but the first which we replace */
+void flx_cache_update(flxCache *c, flxRecord *r, gboolean unique, const flxAddress *a) {
+    flxCacheEntry *e, *t;
+    gchar *txt;
+    
+    g_assert(c);
+    g_assert(r && r->ref >= 1);
 
-            while (e->by_name_next)
-                remove_entry(c, e->by_name_next, TRUE);
+    g_message("cache update: %s", (txt = flx_record_to_string(r)));
+    g_free(txt);
 
-            g_free(e->record->data);
-            e->record->data = g_memdup(r->data, r->size);
-            e->record->size = r->size;
-            e->record->ttl = r->ttl;
+    if (r->ttl == 0) {
 
-        } else {
-            /* Look for exactly the same entry */
+        /* This is a goodbye request */
 
-            for (; e; e = e->by_name_next) {
-                if (e->record->size == r->size &&
-                    !memcmp(e->record->data, r->data, r->size)) {
+        if ((e = flx_cache_lookup_record(c, r))) {
 
-                    /* We found it, so let's update the TTL */
-                    e->record->ttl = r->ttl;
-                    break;
-                }
-            }
+            e->state = FLX_CACHE_FINAL;
+            g_get_current_time(&e->timestamp);
+            e->expiry = e->timestamp;
+            g_time_val_add(&e->expiry, 1000000); /* 1s */
+            update_time_event(c, e);
         }
-    }
 
-    if (!e) {
-        /* No entry found, therefore we create a new one */
-        
-        e = g_new(flxCacheEntry, 1);
-        e->node = NULL;
+    } else {
 
-        e->record = flx_record_ref(r);
-        FLX_LLIST_PREPEND(flxCacheEntry, by_name, t, e);
-        g_hash_table_replace(c->hash_table, e->record->key, e);
-    } 
+        /* This is an update request */
 
-    e->origin = *a;
+        if ((t = e = flx_cache_lookup_key(c, r->key))) {
+        
+            if (unique) {
+                
+                /* For unique records, remove all entries but one */
+                while (e->by_key_next)
+                    remove_entry(c, e->by_key_next);
+                
+            } else {
+                
+                /* For non-unique record, look for exactly the same entry */
+                for (; e; e = e->by_key_next)
+                    if (flx_record_equal_no_ttl(e->record, r))
+                        break;
+            }
+        }
     
-    g_get_current_time(&e->timestamp);
-    e->expiry = e->timestamp;
-    g_time_val_add(&e->expiry, e->record->ttl * 1000000);
+        if (e) {
+            
+/*         g_message("found matching cache entry"); */
+            
+            /* We are the first in the linked list so let's replace the hash table key with the new one */
+            if (e->by_key_prev == NULL)
+                g_hash_table_replace(c->hash_table, r->key, e);
+            
+            /* Notify subscribers */
+            if (!flx_record_equal_no_ttl(e->record, r))
+                flx_subscription_notify(c->server, c->interface, r, FLX_SUBSCRIPTION_CHANGE);    
+            
+            /* Update the record */
+            flx_record_unref(e->record);
+            e->record = flx_record_ref(r);
+            
+        } else {
+            /* No entry found, therefore we create a new one */
+            
+/*         g_message("couldn't find matching cache entry"); */
+            
+            e = g_new(flxCacheEntry, 1);
+            e->cache = c;
+            e->time_event = NULL;
+            e->record = flx_record_ref(r);
+
+            /* Append to hash table */
+            FLX_LLIST_PREPEND(flxCacheEntry, by_key, t, e);
+            g_hash_table_replace(c->hash_table, e->record->key, t);
+
+            /* Append to linked list */
+            FLX_LLIST_PREPEND(flxCacheEntry, entry, c->entries, e);
+
+            /* Notify subscribers */
+            flx_subscription_notify(c->server, c->interface, e->record, FLX_SUBSCRIPTION_NEW);
+        } 
+        
+        e->origin = *a;
+        g_get_current_time(&e->timestamp);
+        next_expiry(c, e, 80);
+        e->state = FLX_CACHE_VALID;
+    }
+}
 
-    e->state = FLX_CACHE_VALID;
+static gpointer drop_key_callback(flxCache *c, flxKey *pattern, flxCacheEntry *e, gpointer userdata) {
+    g_assert(c);
+    g_assert(pattern);
+    g_assert(e);
 
-    return e;
+    remove_entry(c, e);
+    return NULL;
 }
 
 void flx_cache_drop_key(flxCache *c, flxKey *k) {
-    flxCacheEntry *e;
-    
     g_assert(c);
     g_assert(k);
 
-    while ((e = flx_cache_lookup_key(c, k)))
-        remove_entry(c, e, TRUE);
+    flx_cache_walk(c, k, drop_key_callback, NULL);
 }
 
 void flx_cache_drop_record(flxCache *c, flxRecord *r) {
@@ -145,5 +308,39 @@ void flx_cache_drop_record(flxCache *c, flxRecord *r) {
     g_assert(r);
 
     if ((e = flx_cache_lookup_record(c, r))) 
-        remove_entry(c, e, TRUE);
+        remove_entry(c, e);
+}
+
+static void func(gpointer key, gpointer data, gpointer userdata) {
+    flxCacheEntry *e = data;
+    flxKey *k = key;
+    gchar *t;
+
+    t = flx_record_to_string(e->record);
+    fprintf((FILE*) userdata, "%s\n", t);
+    g_free(t);
+}
+
+void flx_cache_dump(flxCache *c, FILE *f) {
+    g_assert(c);
+    g_assert(f);
+
+    fprintf(f, ";;; CACHE DUMP FOLLOWS ;;;\n");
+    g_hash_table_foreach(c->hash_table, func, f);
+}
+
+gboolean flx_cache_entry_half_ttl(flxCache *c, flxCacheEntry *e) {
+    GTimeVal now;
+    guint age;
+    
+    g_assert(c);
+    g_assert(e);
+
+    g_get_current_time(&now);
+
+    age = flx_timeval_diff(&now, &e->timestamp)/1000000;
+
+    g_message("age: %u, ttl/2: %u", age, e->record->ttl);
+    
+    return age >= e->record->ttl/2;
 }