src/datacache/plugin_datacache_heap.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2012, 2015 GNUnet e.V.
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18      Boston, MA 02110-1301, USA.
  19 */
  20
  21 /**
  22  * @file datacache/plugin_datacache_heap.c
  23  * @brief heap-only implementation of a database backend for the datacache
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_util_lib.h"
  28 #include "gnunet_datacache_plugin.h"
  29
  30 #define LOG(kind,...) GNUNET_log_from (kind, "datacache-heap", __VA_ARGS__)
  31
  32 #define LOG_STRERROR_FILE(kind,op,fn) GNUNET_log_from_strerror_file (kind, "datacache-heap", op, fn)
  33
  34
  35
  36 /**
  37  * Context for all functions in this plugin.
  38  */
  39 struct Plugin
  40 {
  41   /**
  42    * Our execution environment.
  43    */
  44   struct GNUNET_DATACACHE_PluginEnvironment *env;
  45
  46   /**
  47    * Our hash map.
  48    */
  49   struct GNUNET_CONTAINER_MultiHashMap *map;
  50
  51   /**
  52    * Heap for expirations.
  53    */
  54   struct GNUNET_CONTAINER_Heap *heap;
  55
  56 };
  57
  58
  59 /**
  60  * Entry in the hash map.
  61  */
  62 struct Value
  63 {
  64   /**
  65    * Key for the entry.
  66    */
  67   struct GNUNET_HashCode key;
  68
  69   /**
  70    * Expiration time.
  71    */
  72   struct GNUNET_TIME_Absolute discard_time;
  73
  74   /**
  75    * Corresponding node in the heap.
  76    */
  77   struct GNUNET_CONTAINER_HeapNode *hn;
  78
  79   /**
  80    * Path information.
  81    */
  82   struct GNUNET_PeerIdentity *path_info;
  83
  84   /**
  85    * Payload (actual payload follows this struct)
  86    */
  87   size_t size;
  88
  89   /**
  90    * Number of entries in @e path_info.
  91    */
  92   unsigned int path_info_len;
  93
  94   /**
  95    * Type of the block.
  96    */
  97   enum GNUNET_BLOCK_Type type;
  98
  99 };
 100
 101
 102 #define OVERHEAD (sizeof (struct Value) + 64)
 103
 104
 105 /**
 106  * Closure for #put_cb().
 107  */
 108 struct PutContext
 109 {
 110   /**
 111    * Expiration time for the new value.
 112    */
 113   struct GNUNET_TIME_Absolute discard_time;
 114
 115   /**
 116    * Data for the new value.
 117    */
 118   const char *data;
 119
 120   /**
 121    * Heap from the plugin.
 122    */
 123   struct GNUNET_CONTAINER_Heap *heap;
 124
 125   /**
 126    * Path information.
 127    */
 128   const struct GNUNET_PeerIdentity *path_info;
 129
 130   /**
 131    * Number of bytes in @e data.
 132    */
 133   size_t size;
 134
 135   /**
 136    * Type of the node.
 137    */
 138   enum GNUNET_BLOCK_Type type;
 139
 140   /**
 141    * Number of entries in @e path_info.
 142    */
 143   unsigned int path_info_len;
 144
 145   /**
 146    * Value to set to #GNUNET_YES if an equivalent block was found.
 147    */
 148   int found;
 149 };
 150
 151
 152 /**
 153  * Function called during PUT to detect if an equivalent block
 154  * already exists.
 155  *
 156  * @param cls the `struct PutContext`
 157  * @param key the key for the value(s)
 158  * @param value an existing value
 159  * @return #GNUNET_YES if not found (to continue to iterate)
 160  */
 161 static int
 162 put_cb (void *cls,
 163         const struct GNUNET_HashCode *key,
 164         void *value)
 165 {
 166   struct PutContext *put_ctx = cls;
 167   struct Value *val = value;
 168
 169   if ( (val->size == put_ctx->size) &&
 170        (val->type == put_ctx->type) &&
 171        (0 == memcmp (&val[1], put_ctx->data, put_ctx->size)) )
 172   {
 173     put_ctx->found = GNUNET_YES;
 174     val->discard_time = GNUNET_TIME_absolute_max (val->discard_time,
 175                                                   put_ctx->discard_time);
 176     /* replace old path with new path */
 177     GNUNET_array_grow (val->path_info,
 178                        val->path_info_len,
 179                        put_ctx->path_info_len);
 180     GNUNET_memcpy (val->path_info,
 181             put_ctx->path_info,
 182             put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity));
 183     GNUNET_CONTAINER_heap_update_cost (put_ctx->heap,
 184                                        val->hn,
 185                                        val->discard_time.abs_value_us);
 186     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 187                 "Got same value for key %s and type %d (size %u vs %u)\n",
 188                 GNUNET_h2s (key),
 189                 val->type,
 190                 (unsigned int) val->size,
 191                 (unsigned int) put_ctx->size);
 192     return GNUNET_NO;
 193   }
 194   return GNUNET_YES;
 195 }
 196
 197
 198 /**
 199  * Store an item in the datastore.
 200  *
 201  * @param cls closure (our `struct Plugin`)
 202  * @param key key to store data under
 203  * @param size number of bytes in @a data
 204  * @param data data to store
 205  * @param type type of the value
 206  * @param discard_time when to discard the value in any case
 207  * @param path_info_len number of entries in @a path_info
 208  * @param path_info a path through the network
 209  * @return 0 if duplicate, -1 on error, number of bytes used otherwise
 210  */
 211 static ssize_t
 212 heap_plugin_put (void *cls,
 213                  const struct GNUNET_HashCode *key,
 214                  size_t size,
 215                  const char *data,
 216                  enum GNUNET_BLOCK_Type type,
 217                  struct GNUNET_TIME_Absolute discard_time,
 218                  unsigned int path_info_len,
 219                  const struct GNUNET_PeerIdentity *path_info)
 220 {
 221   struct Plugin *plugin = cls;
 222   struct Value *val;
 223   struct PutContext put_ctx;
 224
 225   put_ctx.found = GNUNET_NO;
 226   put_ctx.heap = plugin->heap;
 227   put_ctx.data = data;
 228   put_ctx.size = size;
 229   put_ctx.path_info = path_info;
 230   put_ctx.path_info_len = path_info_len;
 231   put_ctx.discard_time = discard_time;
 232   put_ctx.type = type;
 233   GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
 234                                               key,
 235                                               &put_cb,
 236                                               &put_ctx);
 237   if (GNUNET_YES == put_ctx.found)
 238     return 0;
 239   val = GNUNET_malloc (sizeof (struct Value) + size);
 240   GNUNET_memcpy (&val[1], data, size);
 241   val->key = *key;
 242   val->type = type;
 243   val->discard_time = discard_time;
 244   val->size = size;
 245   GNUNET_array_grow (val->path_info,
 246                      val->path_info_len,
 247                      path_info_len);
 248   GNUNET_memcpy (val->path_info,
 249           path_info,
 250           path_info_len * sizeof (struct GNUNET_PeerIdentity));
 251   (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
 252                                             &val->key,
 253                                             val,
 254                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 255   val->hn = GNUNET_CONTAINER_heap_insert (plugin->heap,
 256                                           val,
 257                                           val->discard_time.abs_value_us);
 258   return size + OVERHEAD;
 259 }
 260
 261
 262 /**
 263  * Closure for #get_cb().
 264  */
 265 struct GetContext
 266 {
 267   /**
 268    * Function to call for each result.
 269    */
 270   GNUNET_DATACACHE_Iterator iter;
 271
 272   /**
 273    * Closure for @e iter.
 274    */
 275   void *iter_cls;
 276
 277   /**
 278    * Number of results found.
 279    */
 280   unsigned int cnt;
 281
 282   /**
 283    * Block type requested.
 284    */
 285   enum GNUNET_BLOCK_Type type;
 286 };
 287
 288
 289
 290 /**
 291  * Function called during GET to find matching blocks.
 292  * Only matches by type.
 293  *
 294  * @param cls the `struct GetContext`
 295  * @param key the key for the value(s)
 296  * @param value an existing value
 297  * @return #GNUNET_YES to continue to iterate
 298  */
 299 static int
 300 get_cb (void *cls,
 301         const struct GNUNET_HashCode *key,
 302         void *value)
 303 {
 304   struct GetContext *get_ctx = cls;
 305   struct Value *val = value;
 306   int ret;
 307
 308   if ( (get_ctx->type != val->type) &&
 309        (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
 310     return GNUNET_OK;
 311   if (NULL != get_ctx->iter)
 312     ret = get_ctx->iter (get_ctx->iter_cls,
 313                          key,
 314                          val->size,
 315                          (const char *) &val[1],
 316                          val->type,
 317                          val->discard_time,
 318                          val->path_info_len,
 319                          val->path_info);
 320   else
 321     ret = GNUNET_YES;
 322   get_ctx->cnt++;
 323   return ret;
 324 }
 325
 326
 327 /**
 328  * Iterate over the results for a particular key
 329  * in the datastore.
 330  *
 331  * @param cls closure (our `struct Plugin`)
 332  * @param key
 333  * @param type entries of which type are relevant?
 334  * @param iter maybe NULL (to just count)
 335  * @param iter_cls closure for @a iter
 336  * @return the number of results found
 337  */
 338 static unsigned int
 339 heap_plugin_get (void *cls,
 340                  const struct GNUNET_HashCode *key,
 341                  enum GNUNET_BLOCK_Type type,
 342                  GNUNET_DATACACHE_Iterator iter,
 343                  void *iter_cls)
 344 {
 345   struct Plugin *plugin = cls;
 346   struct GetContext get_ctx;
 347
 348   get_ctx.type = type;
 349   get_ctx.iter = iter;
 350   get_ctx.iter_cls = iter_cls;
 351   get_ctx.cnt = 0;
 352   GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
 353                                               key,
 354                                               &get_cb,
 355                                               &get_ctx);
 356   return get_ctx.cnt;
 357 }
 358
 359
 360 /**
 361  * Delete the entry with the lowest expiration value
 362  * from the datacache right now.
 363  *
 364  * @param cls closure (our `struct Plugin`)
 365  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
 366  */
 367 static int
 368 heap_plugin_del (void *cls)
 369 {
 370   struct Plugin *plugin = cls;
 371   struct Value *val;
 372
 373   val = GNUNET_CONTAINER_heap_remove_root (plugin->heap);
 374   if (NULL == val)
 375     return GNUNET_SYSERR;
 376   GNUNET_assert (GNUNET_YES ==
 377                  GNUNET_CONTAINER_multihashmap_remove (plugin->map,
 378                                                        &val->key,
 379                                                        val));
 380   plugin->env->delete_notify (plugin->env->cls,
 381                               &val->key,
 382                               val->size + OVERHEAD);
 383   GNUNET_free_non_null (val->path_info);
 384   GNUNET_free (val);
 385   return GNUNET_OK;
 386 }
 387
 388
 389 /**
 390  * Return a random value from the datastore.
 391  *
 392  * @param cls closure (our `struct Plugin`)
 393  * @param iter maybe NULL (to just count)
 394  * @param iter_cls closure for @a iter
 395  * @return the number of results found
 396  */
 397 static unsigned int
 398 heap_plugin_get_random (void *cls,
 399                         GNUNET_DATACACHE_Iterator iter,
 400                         void *iter_cls)
 401 {
 402   struct Plugin *plugin = cls;
 403   struct GetContext get_ctx;
 404
 405   get_ctx.type = GNUNET_BLOCK_TYPE_ANY;
 406   get_ctx.iter = iter;
 407   get_ctx.iter_cls = iter_cls;
 408   get_ctx.cnt = 0;
 409   GNUNET_CONTAINER_multihashmap_get_random (plugin->map,
 410                                             &get_cb,
 411                                             &get_ctx);
 412   return get_ctx.cnt;
 413 }
 414
 415
 416 /**
 417  * Iterate over the results that are "close" to a particular key in
 418  * the datacache.  "close" is defined as numerically larger than @a
 419  * key (when interpreted as a circular address space), with small
 420  * distance.
 421  *
 422  * @param cls closure (internal context for the plugin)
 423  * @param key area of the keyspace to look into
 424  * @param num_results number of results that should be returned to @a iter
 425  * @param iter maybe NULL (to just count)
 426  * @param iter_cls closure for @a iter
 427  * @return the number of results found
 428  */
 429 static unsigned int
 430 heap_plugin_get_closest (void *cls,
 431                          const struct GNUNET_HashCode *key,
 432                          unsigned int num_results,
 433                          GNUNET_DATACACHE_Iterator iter,
 434                          void *iter_cls)
 435 {
 436   GNUNET_break (0); // not implemented!
 437   return 0;
 438 }
 439
 440
 441 /**
 442  * Entry point for the plugin.
 443  *
 444  * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`)
 445  * @return the plugin's closure (our `struct Plugin`)
 446  */
 447 void *
 448 libgnunet_plugin_datacache_heap_init (void *cls)
 449 {
 450   struct GNUNET_DATACACHE_PluginEnvironment *env = cls;
 451   struct GNUNET_DATACACHE_PluginFunctions *api;
 452   struct Plugin *plugin;
 453
 454   plugin = GNUNET_new (struct Plugin);
 455   plugin->map = GNUNET_CONTAINER_multihashmap_create (1024,  /* FIXME: base on quota! */
 456                                                       GNUNET_YES);
 457   plugin->heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 458   plugin->env = env;
 459   api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
 460   api->cls = plugin;
 461   api->get = &heap_plugin_get;
 462   api->put = &heap_plugin_put;
 463   api->del = &heap_plugin_del;
 464   api->get_random = &heap_plugin_get_random;
 465   api->get_closest = &heap_plugin_get_closest;
 466   LOG (GNUNET_ERROR_TYPE_INFO,
 467        _("Heap datacache running\n"));
 468   return api;
 469 }
 470
 471
 472 /**
 473  * Exit point from the plugin.
 474  *
 475  * @param cls closure (our "struct Plugin")
 476  * @return NULL
 477  */
 478 void *
 479 libgnunet_plugin_datacache_heap_done (void *cls)
 480 {
 481   struct GNUNET_DATACACHE_PluginFunctions *api = cls;
 482   struct Plugin *plugin = api->cls;
 483   struct Value *val;
 484
 485   while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heap)))
 486   {
 487     GNUNET_assert (GNUNET_YES ==
 488                    GNUNET_CONTAINER_multihashmap_remove (plugin->map,
 489                                                          &val->key,
 490                                                          val));
 491     GNUNET_free_non_null (val->path_info);
 492     GNUNET_free (val);
 493   }
 494   GNUNET_CONTAINER_heap_destroy (plugin->heap);
 495   GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
 496   GNUNET_free (plugin);
 497   GNUNET_free (api);
 498   return NULL;
 499 }
 500
 501
 502
 503 /* end of plugin_datacache_heap.c */