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 it
   6      under the terms of the GNU General Public License as published
   7      by the Free Software Foundation, either version 3 of the License,
   8      or (at your 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      Affero General Public License for more details.
  14 */
  15
  16 /**
  17  * @file datacache/plugin_datacache_heap.c
  18  * @brief heap-only implementation of a database backend for the datacache
  19  * @author Christian Grothoff
  20  */
  21 #include "platform.h"
  22 #include "gnunet_util_lib.h"
  23 #include "gnunet_datacache_plugin.h"
  24
  25 #define LOG(kind,...) GNUNET_log_from (kind, "datacache-heap", __VA_ARGS__)
  26
  27 #define LOG_STRERROR_FILE(kind,op,fn) GNUNET_log_from_strerror_file (kind, "datacache-heap", op, fn)
  28
  29 #define NUM_HEAPS 24
  30
  31 /**
  32  * Context for all functions in this plugin.
  33  */
  34 struct Plugin
  35 {
  36   /**
  37    * Our execution environment.
  38    */
  39   struct GNUNET_DATACACHE_PluginEnvironment *env;
  40
  41   /**
  42    * Our hash map.
  43    */
  44   struct GNUNET_CONTAINER_MultiHashMap *map;
  45
  46   /**
  47    * Heaps sorted by distance.
  48    */
  49   struct GNUNET_CONTAINER_Heap *heaps[NUM_HEAPS];
  50
  51 };
  52
  53
  54 /**
  55  * Entry in the hash map.
  56  */
  57 struct Value
  58 {
  59   /**
  60    * Key for the entry.
  61    */
  62   struct GNUNET_HashCode key;
  63
  64   /**
  65    * Expiration time.
  66    */
  67   struct GNUNET_TIME_Absolute discard_time;
  68
  69   /**
  70    * Corresponding node in the heap.
  71    */
  72   struct GNUNET_CONTAINER_HeapNode *hn;
  73
  74   /**
  75    * Path information.
  76    */
  77   struct GNUNET_PeerIdentity *path_info;
  78
  79   /**
  80    * Payload (actual payload follows this struct)
  81    */
  82   size_t size;
  83
  84   /**
  85    * Number of entries in @e path_info.
  86    */
  87   unsigned int path_info_len;
  88
  89   /**
  90    * How close is the hash to us? Determines which heap we are in!
  91    */
  92   uint32_t distance;
  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    * Path information.
 122    */
 123   const struct GNUNET_PeerIdentity *path_info;
 124
 125   /**
 126    * Number of bytes in @e data.
 127    */
 128   size_t size;
 129
 130   /**
 131    * Type of the node.
 132    */
 133   enum GNUNET_BLOCK_Type type;
 134
 135   /**
 136    * Number of entries in @e path_info.
 137    */
 138   unsigned int path_info_len;
 139
 140   /**
 141    * Value to set to #GNUNET_YES if an equivalent block was found.
 142    */
 143   int found;
 144 };
 145
 146
 147 /**
 148  * Function called during PUT to detect if an equivalent block
 149  * already exists.
 150  *
 151  * @param cls the `struct PutContext`
 152  * @param key the key for the value(s)
 153  * @param value an existing value
 154  * @return #GNUNET_YES if not found (to continue to iterate)
 155  */
 156 static int
 157 put_cb (void *cls,
 158         const struct GNUNET_HashCode *key,
 159         void *value)
 160 {
 161   struct PutContext *put_ctx = cls;
 162   struct Value *val = value;
 163
 164   if ( (val->size == put_ctx->size) &&
 165        (val->type == put_ctx->type) &&
 166        (0 == memcmp (&val[1],
 167                      put_ctx->data,
 168                      put_ctx->size)) )
 169   {
 170     put_ctx->found = GNUNET_YES;
 171     val->discard_time = GNUNET_TIME_absolute_max (val->discard_time,
 172                                                   put_ctx->discard_time);
 173     /* replace old path with new path */
 174     GNUNET_array_grow (val->path_info,
 175                        val->path_info_len,
 176                        put_ctx->path_info_len);
 177     GNUNET_memcpy (val->path_info,
 178                    put_ctx->path_info,
 179                    put_ctx->path_info_len * sizeof (struct GNUNET_PeerIdentity));
 180     GNUNET_CONTAINER_heap_update_cost (val->hn,
 181                                        val->discard_time.abs_value_us);
 182     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 183                 "Got same value for key %s and type %d (size %u vs %u)\n",
 184                 GNUNET_h2s (key),
 185                 val->type,
 186                 (unsigned int) val->size,
 187                 (unsigned int) put_ctx->size);
 188     return GNUNET_NO;
 189   }
 190   return GNUNET_YES;
 191 }
 192
 193
 194 /**
 195  * Store an item in the datastore.
 196  *
 197  * @param cls closure (our `struct Plugin`)
 198  * @param key key to store data under
 199  * @param xor_distance how close is @a key to our PID?
 200  * @param size number of bytes in @a data
 201  * @param data data to store
 202  * @param type type of the value
 203  * @param discard_time when to discard the value in any case
 204  * @param path_info_len number of entries in @a path_info
 205  * @param path_info a path through the network
 206  * @return 0 if duplicate, -1 on error, number of bytes used otherwise
 207  */
 208 static ssize_t
 209 heap_plugin_put (void *cls,
 210                  const struct GNUNET_HashCode *key,
 211                  uint32_t xor_distance,
 212                  size_t size,
 213                  const char *data,
 214                  enum GNUNET_BLOCK_Type type,
 215                  struct GNUNET_TIME_Absolute discard_time,
 216                  unsigned int path_info_len,
 217                  const struct GNUNET_PeerIdentity *path_info)
 218 {
 219   struct Plugin *plugin = cls;
 220   struct Value *val;
 221   struct PutContext put_ctx;
 222
 223   put_ctx.found = GNUNET_NO;
 224   put_ctx.data = data;
 225   put_ctx.size = size;
 226   put_ctx.path_info = path_info;
 227   put_ctx.path_info_len = path_info_len;
 228   put_ctx.discard_time = discard_time;
 229   put_ctx.type = type;
 230   GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
 231                                               key,
 232                                               &put_cb,
 233                                               &put_ctx);
 234   if (GNUNET_YES == put_ctx.found)
 235     return 0;
 236   val = GNUNET_malloc (sizeof (struct Value) + size);
 237   GNUNET_memcpy (&val[1],
 238                  data,
 239                  size);
 240   val->key = *key;
 241   val->type = type;
 242   val->discard_time = discard_time;
 243   val->size = size;
 244   if (xor_distance >= NUM_HEAPS)
 245     val->distance = NUM_HEAPS - 1;
 246   else
 247     val->distance = xor_distance;
 248   GNUNET_array_grow (val->path_info,
 249                      val->path_info_len,
 250                      path_info_len);
 251   GNUNET_memcpy (val->path_info,
 252                  path_info,
 253                  path_info_len * sizeof (struct GNUNET_PeerIdentity));
 254   (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
 255                                             &val->key,
 256                                             val,
 257                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 258   val->hn = GNUNET_CONTAINER_heap_insert (plugin->heaps[val->distance],
 259                                           val,
 260                                           val->discard_time.abs_value_us);
 261   return size + OVERHEAD;
 262 }
 263
 264
 265 /**
 266  * Closure for #get_cb().
 267  */
 268 struct GetContext
 269 {
 270   /**
 271    * Function to call for each result.
 272    */
 273   GNUNET_DATACACHE_Iterator iter;
 274
 275   /**
 276    * Closure for @e iter.
 277    */
 278   void *iter_cls;
 279
 280   /**
 281    * Number of results found.
 282    */
 283   unsigned int cnt;
 284
 285   /**
 286    * Block type requested.
 287    */
 288   enum GNUNET_BLOCK_Type type;
 289 };
 290
 291
 292
 293 /**
 294  * Function called during GET to find matching blocks.
 295  * Only matches by type.
 296  *
 297  * @param cls the `struct GetContext`
 298  * @param key the key for the value(s)
 299  * @param value an existing value
 300  * @return #GNUNET_YES to continue to iterate
 301  */
 302 static int
 303 get_cb (void *cls,
 304         const struct GNUNET_HashCode *key,
 305         void *value)
 306 {
 307   struct GetContext *get_ctx = cls;
 308   struct Value *val = value;
 309   int ret;
 310
 311   if ( (get_ctx->type != val->type) &&
 312        (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
 313     return GNUNET_OK;
 314   if (NULL != get_ctx->iter)
 315     ret = get_ctx->iter (get_ctx->iter_cls,
 316                          key,
 317                          val->size,
 318                          (const char *) &val[1],
 319                          val->type,
 320                          val->discard_time,
 321                          val->path_info_len,
 322                          val->path_info);
 323   else
 324     ret = GNUNET_YES;
 325   get_ctx->cnt++;
 326   return ret;
 327 }
 328
 329
 330 /**
 331  * Iterate over the results for a particular key
 332  * in the datastore.
 333  *
 334  * @param cls closure (our `struct Plugin`)
 335  * @param key
 336  * @param type entries of which type are relevant?
 337  * @param iter maybe NULL (to just count)
 338  * @param iter_cls closure for @a iter
 339  * @return the number of results found
 340  */
 341 static unsigned int
 342 heap_plugin_get (void *cls,
 343                  const struct GNUNET_HashCode *key,
 344                  enum GNUNET_BLOCK_Type type,
 345                  GNUNET_DATACACHE_Iterator iter,
 346                  void *iter_cls)
 347 {
 348   struct Plugin *plugin = cls;
 349   struct GetContext get_ctx;
 350
 351   get_ctx.type = type;
 352   get_ctx.iter = iter;
 353   get_ctx.iter_cls = iter_cls;
 354   get_ctx.cnt = 0;
 355   GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
 356                                               key,
 357                                               &get_cb,
 358                                               &get_ctx);
 359   return get_ctx.cnt;
 360 }
 361
 362
 363 /**
 364  * Delete the entry with the lowest expiration value
 365  * from the datacache right now.
 366  *
 367  * @param cls closure (our `struct Plugin`)
 368  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
 369  */
 370 static int
 371 heap_plugin_del (void *cls)
 372 {
 373   struct Plugin *plugin = cls;
 374   struct Value *val;
 375
 376   for (unsigned int i=0;i<NUM_HEAPS;i++)
 377   {
 378     val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i]);
 379     if (NULL != val)
 380       break;
 381   }
 382   if (NULL == val)
 383     return GNUNET_SYSERR;
 384   GNUNET_assert (GNUNET_YES ==
 385                  GNUNET_CONTAINER_multihashmap_remove (plugin->map,
 386                                                        &val->key,
 387                                                        val));
 388   plugin->env->delete_notify (plugin->env->cls,
 389                               &val->key,
 390                               val->size + OVERHEAD);
 391   GNUNET_free_non_null (val->path_info);
 392   GNUNET_free (val);
 393   return GNUNET_OK;
 394 }
 395
 396
 397 /**
 398  * Return a random value from the datastore.
 399  *
 400  * @param cls closure (our `struct Plugin`)
 401  * @param iter maybe NULL (to just count)
 402  * @param iter_cls closure for @a iter
 403  * @return the number of results found
 404  */
 405 static unsigned int
 406 heap_plugin_get_random (void *cls,
 407                         GNUNET_DATACACHE_Iterator iter,
 408                         void *iter_cls)
 409 {
 410   struct Plugin *plugin = cls;
 411   struct GetContext get_ctx;
 412
 413   get_ctx.type = GNUNET_BLOCK_TYPE_ANY;
 414   get_ctx.iter = iter;
 415   get_ctx.iter_cls = iter_cls;
 416   get_ctx.cnt = 0;
 417   GNUNET_CONTAINER_multihashmap_get_random (plugin->map,
 418                                             &get_cb,
 419                                             &get_ctx);
 420   return get_ctx.cnt;
 421 }
 422
 423
 424 /**
 425  * Closure for #find_closest().
 426  */
 427 struct GetClosestContext
 428 {
 429   struct Value **values;
 430
 431   unsigned int num_results;
 432
 433   const struct GNUNET_HashCode *key;
 434 };
 435
 436
 437 static int
 438 find_closest (void *cls,
 439               const struct GNUNET_HashCode *key,
 440               void *value)
 441 {
 442   struct GetClosestContext *gcc = cls;
 443   struct Value *val = value;
 444   unsigned int j;
 445
 446   if (1 != GNUNET_CRYPTO_hash_cmp (key,
 447                                    gcc->key))
 448     return GNUNET_OK; /* useless */
 449   j = gcc->num_results;
 450   for (unsigned int i=0;i<gcc->num_results;i++)
 451   {
 452     if (NULL == gcc->values[i])
 453     {
 454       j = i;
 455       break;
 456     }
 457     if (1 == GNUNET_CRYPTO_hash_cmp (&gcc->values[i]->key,
 458                                      key))
 459     {
 460       j = i;
 461       break;
 462     }
 463   }
 464   if (j == gcc->num_results)
 465     return GNUNET_OK;
 466   gcc->values[j] = val;
 467   return GNUNET_OK;
 468 }
 469
 470
 471 /**
 472  * Iterate over the results that are "close" to a particular key in
 473  * the datacache.  "close" is defined as numerically larger than @a
 474  * key (when interpreted as a circular address space), with small
 475  * distance.
 476  *
 477  * @param cls closure (internal context for the plugin)
 478  * @param key area of the keyspace to look into
 479  * @param num_results number of results that should be returned to @a iter
 480  * @param iter maybe NULL (to just count)
 481  * @param iter_cls closure for @a iter
 482  * @return the number of results found
 483  */
 484 static unsigned int
 485 heap_plugin_get_closest (void *cls,
 486                          const struct GNUNET_HashCode *key,
 487                          unsigned int num_results,
 488                          GNUNET_DATACACHE_Iterator iter,
 489                          void *iter_cls)
 490 {
 491   struct Plugin *plugin = cls;
 492   struct Value *values[num_results];
 493   struct GetClosestContext gcc = {
 494     .values = values,
 495     .num_results = num_results,
 496     .key = key
 497   };
 498   GNUNET_CONTAINER_multihashmap_iterate (plugin->map,
 499                                          &find_closest,
 500                                          &gcc);
 501   for (unsigned int i=0;i<num_results;i++)
 502   {
 503     if (NULL == values[i])
 504       return i;
 505     iter (iter_cls,
 506           &values[i]->key,
 507           values[i]->size,
 508           (void *) &values[i][1],
 509           values[i]->type,
 510           values[i]->discard_time,
 511           values[i]->path_info_len,
 512           values[i]->path_info);
 513   }
 514   return num_results;
 515 }
 516
 517
 518 /**
 519  * Entry point for the plugin.
 520  *
 521  * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`)
 522  * @return the plugin's closure (our `struct Plugin`)
 523  */
 524 void *
 525 libgnunet_plugin_datacache_heap_init (void *cls)
 526 {
 527   struct GNUNET_DATACACHE_PluginEnvironment *env = cls;
 528   struct GNUNET_DATACACHE_PluginFunctions *api;
 529   struct Plugin *plugin;
 530
 531   plugin = GNUNET_new (struct Plugin);
 532   plugin->map = GNUNET_CONTAINER_multihashmap_create (1024,  /* FIXME: base on quota! */
 533                                                       GNUNET_YES);
 534   for (unsigned int i=0;i<NUM_HEAPS;i++)
 535     plugin->heaps[i] = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
 536   plugin->env = env;
 537   api = GNUNET_new (struct GNUNET_DATACACHE_PluginFunctions);
 538   api->cls = plugin;
 539   api->get = &heap_plugin_get;
 540   api->put = &heap_plugin_put;
 541   api->del = &heap_plugin_del;
 542   api->get_random = &heap_plugin_get_random;
 543   api->get_closest = &heap_plugin_get_closest;
 544   LOG (GNUNET_ERROR_TYPE_INFO,
 545        _("Heap datacache running\n"));
 546   return api;
 547 }
 548
 549
 550 /**
 551  * Exit point from the plugin.
 552  *
 553  * @param cls closure (our "struct Plugin")
 554  * @return NULL
 555  */
 556 void *
 557 libgnunet_plugin_datacache_heap_done (void *cls)
 558 {
 559   struct GNUNET_DATACACHE_PluginFunctions *api = cls;
 560   struct Plugin *plugin = api->cls;
 561   struct Value *val;
 562
 563   for (unsigned int i=0;i<NUM_HEAPS;i++)
 564   {
 565     while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heaps[i])))
 566     {
 567       GNUNET_assert (GNUNET_YES ==
 568                      GNUNET_CONTAINER_multihashmap_remove (plugin->map,
 569                                                            &val->key,
 570                                                            val));
 571       GNUNET_free_non_null (val->path_info);
 572       GNUNET_free (val);
 573     }
 574     GNUNET_CONTAINER_heap_destroy (plugin->heaps[i]);
 575   }
 576   GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
 577   GNUNET_free (plugin);
 578   GNUNET_free (api);
 579   return NULL;
 580 }
 581
 582
 583
 584 /* end of plugin_datacache_heap.c */