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