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