missing fi
[oweals/gnunet.git] / src / datacache / plugin_datacache_heap.c
1 /*
2      This file is part of GNUnet
3      (C) 2012 Christian Grothoff (and other contributing authors)
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., 59 Temple Place - Suite 330,
18      Boston, MA 02111-1307, 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 '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 '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 '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     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 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, const struct GNUNET_HashCode * key, size_t size,
213                  const char *data, enum GNUNET_BLOCK_Type type,
214                  struct GNUNET_TIME_Absolute discard_time,
215                  unsigned int path_info_len,
216                  const struct GNUNET_PeerIdentity *path_info)
217 {
218   struct Plugin *plugin = cls;
219   struct Value *val;
220   struct PutContext put_ctx;
221
222   put_ctx.found = GNUNET_NO;
223   put_ctx.heap = plugin->heap;
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   memcpy (&val[1], data, size);
238   val->key = *key;
239   val->type = type;
240   val->discard_time = discard_time;
241   val->size = size;
242   GNUNET_array_grow (val->path_info,
243                      val->path_info_len,
244                      path_info_len);
245   memcpy (val->path_info, path_info,
246           path_info_len * sizeof (struct GNUNET_PeerIdentity));
247   (void) GNUNET_CONTAINER_multihashmap_put (plugin->map,
248                                             &val->key,
249                                             val,
250                                             GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
251   val->hn = GNUNET_CONTAINER_heap_insert (plugin->heap,
252                                           val,
253                                           val->discard_time.abs_value_us);
254   return size + OVERHEAD;
255 }
256
257
258 /**
259  * Closure for 'get_cb'.
260  */
261 struct GetContext
262 {
263   /**
264    * Function to call for each result.
265    */
266   GNUNET_DATACACHE_Iterator iter;
267
268   /**
269    * Closure for 'iter'.
270    */
271   void *iter_cls;
272
273   /**
274    * Number of results found.
275    */
276   unsigned int cnt;
277
278   /**
279    * Block type requested.
280    */
281   enum GNUNET_BLOCK_Type type;
282 };
283
284
285
286 /**
287  * Function called during GET to find matching blocks.
288  * Only matches by type.
289  *
290  * @param cls the 'struct GetContext'
291  * @param key the key for the value(s)
292  * @param value an existing value
293  * @return GNUNET_YES to continue to iterate
294  */
295 static int
296 get_cb (void *cls,
297         const struct GNUNET_HashCode *key,
298         void *value)
299 {
300   struct GetContext *get_ctx = cls;
301   struct Value *val = value;
302   int ret;
303
304   if ( (get_ctx->type != val->type) &&
305        (GNUNET_BLOCK_TYPE_ANY != get_ctx->type) )
306     return GNUNET_OK;
307   if (NULL != get_ctx->iter)
308     ret = get_ctx->iter (get_ctx->iter_cls,
309                          key,
310                          val->size,
311                          (const char *) &val[1],
312                          val->type,
313                        val->discard_time,
314                          val->path_info_len,
315                          val->path_info);
316   else
317     ret = GNUNET_YES;
318   get_ctx->cnt++;
319   return ret;
320 }
321
322
323 /**
324  * Iterate over the results for a particular key
325  * in the datastore.
326  *
327  * @param cls closure (our "struct Plugin")
328  * @param key
329  * @param type entries of which type are relevant?
330  * @param iter maybe NULL (to just count)
331  * @param iter_cls closure for iter
332  * @return the number of results found
333  */
334 static unsigned int
335 heap_plugin_get (void *cls, const struct GNUNET_HashCode * key,
336                    enum GNUNET_BLOCK_Type type, GNUNET_DATACACHE_Iterator iter,
337                    void *iter_cls)
338 {
339   struct Plugin *plugin = cls;
340   struct GetContext get_ctx;
341
342   get_ctx.type = type;
343   get_ctx.iter = iter;
344   get_ctx.iter_cls = iter_cls;
345   get_ctx.cnt = 0;
346   GNUNET_CONTAINER_multihashmap_get_multiple (plugin->map,
347                                               key,
348                                               get_cb,
349                                               &get_ctx);
350   return get_ctx.cnt;
351 }
352
353
354 /**
355  * Delete the entry with the lowest expiration value
356  * from the datacache right now.
357  *
358  * @param cls closure (our "struct Plugin")
359  * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
360  */
361 static int
362 heap_plugin_del (void *cls)
363 {
364   struct Plugin *plugin = cls;
365   struct Value *val;
366
367   val = GNUNET_CONTAINER_heap_remove_root (plugin->heap);
368   if (NULL == val)
369     return GNUNET_SYSERR;
370   GNUNET_assert (GNUNET_YES ==
371                  GNUNET_CONTAINER_multihashmap_remove (plugin->map,
372                                                        &val->key,
373                                                        val));
374   plugin->env->delete_notify (plugin->env->cls,
375                               &val->key,
376                               val->size + OVERHEAD);
377   GNUNET_free_non_null (val->path_info);
378   GNUNET_free (val);
379   return GNUNET_OK;
380 }
381
382
383 /**
384  * Entry point for the plugin.
385  *
386  * @param cls closure (the `struct GNUNET_DATACACHE_PluginEnvironmnet`)
387  * @return the plugin's closure (our `struct Plugin`)
388  */
389 void *
390 libgnunet_plugin_datacache_heap_init (void *cls)
391 {
392   struct GNUNET_DATACACHE_PluginEnvironment *env = cls;
393   struct GNUNET_DATACACHE_PluginFunctions *api;
394   struct Plugin *plugin;
395
396   plugin = GNUNET_malloc (sizeof (struct Plugin));
397   plugin->map = GNUNET_CONTAINER_multihashmap_create (1024,  /* FIXME: base on quota! */
398                                                       GNUNET_YES);
399   plugin->heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
400   plugin->env = env;
401   api = GNUNET_malloc (sizeof (struct GNUNET_DATACACHE_PluginFunctions));
402   api->cls = plugin;
403   api->get = &heap_plugin_get;
404   api->put = &heap_plugin_put;
405   api->del = &heap_plugin_del;
406   LOG (GNUNET_ERROR_TYPE_INFO, _("Heap datacache running\n"));
407   return api;
408 }
409
410
411 /**
412  * Exit point from the plugin.
413  *
414  * @param cls closure (our "struct Plugin")
415  * @return NULL
416  */
417 void *
418 libgnunet_plugin_datacache_heap_done (void *cls)
419 {
420   struct GNUNET_DATACACHE_PluginFunctions *api = cls;
421   struct Plugin *plugin = api->cls;
422   struct Value *val;
423
424   while (NULL != (val = GNUNET_CONTAINER_heap_remove_root (plugin->heap)))
425   {
426     GNUNET_assert (GNUNET_YES ==
427                    GNUNET_CONTAINER_multihashmap_remove (plugin->map,
428                                                          &val->key,
429                                                          val));
430     GNUNET_free_non_null (val->path_info);
431     GNUNET_free (val);
432   }
433   GNUNET_CONTAINER_heap_destroy (plugin->heap);
434   GNUNET_CONTAINER_multihashmap_destroy (plugin->map);
435   GNUNET_free (plugin);
436   GNUNET_free (api);
437   return NULL;
438 }
439
440
441
442 /* end of plugin_datacache_heap.c */