2 This file is part of GNUnet
3 Copyright (C) 2003-2013 GNUnet e.V.
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.
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.
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.
22 * @file fs/fs_namespace.c
23 * @brief publishing to namespaces, and tracking updateable entries
25 * @author Christian Grothoff
28 #include "gnunet_constants.h"
29 #include "gnunet_signatures.h"
30 #include "gnunet_util_lib.h"
31 #include "gnunet_fs_service.h"
33 #include "fs_publish_ublock.h"
37 * Information about an (updateable) node in the
40 struct NamespaceUpdateNode
43 * Identifier for this node.
48 * Identifier of children of this node.
53 * Metadata for this entry.
55 struct GNUNET_CONTAINER_MetaData *md;
58 * URI of this entry in the namespace.
60 struct GNUNET_FS_Uri *uri;
63 * Namespace update generation ID. Used to ensure
64 * freshness of the tree_id.
69 * TREE this entry belongs to (if nug is current).
77 * Handle to update information for a namespace.
79 struct GNUNET_FS_UpdateInformationGraph
83 * Handle to the FS service context.
85 struct GNUNET_FS_Handle *h;
88 * Array with information about nodes in the namespace.
90 struct NamespaceUpdateNode **update_nodes;
93 * Private key for the namespace.
95 struct GNUNET_CRYPTO_EcdsaPrivateKey ns;
98 * Hash map mapping identifiers of update nodes
99 * to the update nodes (initialized on-demand).
101 struct GNUNET_CONTAINER_MultiHashMap *update_map;
104 * Size of the update nodes array.
106 unsigned int update_node_count;
114 * Generator for unique nug numbers.
116 unsigned int nug_gen;
121 * Return the name of the directory in which we store
122 * the update information graph for the given local namespace.
124 * @param h file-sharing handle
125 * @param ns namespace handle
126 * @return NULL on error, otherwise the name of the directory
129 get_update_information_directory (struct GNUNET_FS_Handle *h,
130 const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns)
134 struct GNUNET_CRYPTO_EcdsaPublicKey pub;
135 struct GNUNET_HashCode hc;
136 struct GNUNET_CRYPTO_HashAsciiEncoded enc;
139 GNUNET_CONFIGURATION_get_value_filename (h->cfg, "FS", "UPDATE_DIR",
142 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
146 GNUNET_CRYPTO_ecdsa_key_get_public (ns, &pub);
147 GNUNET_CRYPTO_hash (&pub, sizeof (pub), &hc);
148 GNUNET_CRYPTO_hash_to_enc (&hc,
150 GNUNET_asprintf (&ret, "%s%s%s",
153 (const char *) enc.encoding);
160 * Release memory occupied by UIG datastructure.
162 * @param uig data structure to free
165 free_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
168 struct NamespaceUpdateNode *nsn;
170 for (i = 0; i < uig->update_node_count; i++)
172 nsn = uig->update_nodes[i];
173 GNUNET_CONTAINER_meta_data_destroy (nsn->md);
174 GNUNET_FS_uri_destroy (nsn->uri);
175 GNUNET_free (nsn->id);
176 GNUNET_free (nsn->update);
179 GNUNET_array_grow (uig->update_nodes, uig->update_node_count,
181 if (NULL != uig->update_map)
182 GNUNET_CONTAINER_multihashmap_destroy (uig->update_map);
188 * Write a namespace's update node graph to a file.
190 * @param uig update information graph to dump
193 write_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
196 struct GNUNET_BIO_WriteHandle *wh;
198 struct NamespaceUpdateNode *n;
201 fn = get_update_information_directory (uig->h,
203 wh = GNUNET_BIO_write_open (fn);
206 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
207 _("Failed to open `%s' for writing: %s\n"),
213 if (GNUNET_OK != GNUNET_BIO_write_int32 (wh, uig->update_node_count))
215 for (i = 0; i < uig->update_node_count; i++)
217 n = uig->update_nodes[i];
218 uris = GNUNET_FS_uri_to_string (n->uri);
219 if ((GNUNET_OK != GNUNET_BIO_write_string (wh, n->id)) ||
220 (GNUNET_OK != GNUNET_BIO_write_meta_data (wh, n->md)) ||
221 (GNUNET_OK != GNUNET_BIO_write_string (wh, n->update)) ||
222 (GNUNET_OK != GNUNET_BIO_write_string (wh, uris)))
230 if (GNUNET_OK != GNUNET_BIO_write_close (wh))
231 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
232 _("Failed to write `%s': %s\n"),
240 * Read the namespace update node graph from a file.
242 * @param h FS handle to use
243 * @param ns namespace to read
244 * @return update graph, never NULL
246 static struct GNUNET_FS_UpdateInformationGraph *
247 read_update_information_graph (struct GNUNET_FS_Handle *h,
248 const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns)
250 struct GNUNET_FS_UpdateInformationGraph *uig;
252 struct GNUNET_BIO_ReadHandle *rh;
254 struct NamespaceUpdateNode *n;
259 uig = GNUNET_new (struct GNUNET_FS_UpdateInformationGraph);
262 fn = get_update_information_directory (h, ns);
263 if (GNUNET_YES != GNUNET_DISK_file_test (fn))
268 rh = GNUNET_BIO_read_open (fn);
274 if (GNUNET_OK != GNUNET_BIO_read_int32 (rh, &count))
279 if (count > 1024 * 1024)
287 GNUNET_malloc (count * sizeof (struct NamespaceUpdateNode *));
289 for (i = 0; i < count; i++)
291 n = GNUNET_new (struct NamespaceUpdateNode);
292 if ((GNUNET_OK != GNUNET_BIO_read_string (rh, "identifier", &n->id, 1024))
293 || (GNUNET_OK != GNUNET_BIO_read_meta_data (rh, "meta", &n->md)) ||
295 GNUNET_BIO_read_string (rh, "update-id", &n->update, 1024)) ||
296 (GNUNET_OK != GNUNET_BIO_read_string (rh, "uri", &uris, 1024 * 2)))
299 GNUNET_free_non_null (n->id);
300 GNUNET_free_non_null (n->update);
302 GNUNET_CONTAINER_meta_data_destroy (n->md);
306 n->uri = GNUNET_FS_uri_parse (uris, &emsg);
313 GNUNET_free_non_null (n->update);
314 GNUNET_CONTAINER_meta_data_destroy (n->md);
318 uig->update_nodes[i] = n;
320 uig->update_node_count = i;
322 if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
324 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to read `%s': %s\n"),
334 * Context for the SKS publication.
336 struct GNUNET_FS_PublishSksContext
340 * URI of the new entry in the namespace.
342 struct GNUNET_FS_Uri *uri;
345 * Namespace update node to add to namespace on success (or to be
346 * deleted if publishing failed).
348 struct NamespaceUpdateNode *nsn;
351 * Namespace we're publishing to.
353 struct GNUNET_CRYPTO_EcdsaPrivateKey ns;
356 * Handle to the datastore.
358 struct GNUNET_DATASTORE_Handle *dsh;
363 struct GNUNET_FS_Handle *h;
366 * Function to call once we're done.
368 GNUNET_FS_PublishContinuation cont;
376 * Handle for our UBlock operation request.
378 struct GNUNET_FS_PublishUblockContext *uc;
383 * Function called by the UBlock construction with
384 * the result from the PUT (UBlock) request.
386 * @param cls closure of type "struct GNUNET_FS_PublishSksContext*"
387 * @param msg error message (or NULL)
390 sks_publish_cont (void *cls,
393 struct GNUNET_FS_PublishSksContext *psc = cls;
394 struct GNUNET_FS_UpdateInformationGraph *uig;
399 if (NULL != psc->cont)
400 psc->cont (psc->cont_cls, NULL, msg);
401 GNUNET_FS_publish_sks_cancel (psc);
404 if (NULL != psc->nsn)
406 /* FIXME: this can be done much more
407 * efficiently by simply appending to the
408 * file and overwriting the 4-byte header */
409 uig = read_update_information_graph (psc->h,
411 GNUNET_array_append (uig->update_nodes,
412 uig->update_node_count,
415 write_update_information_graph (uig);
416 free_update_information_graph (uig);
418 if (NULL != psc->cont)
419 psc->cont (psc->cont_cls, psc->uri, NULL);
420 GNUNET_FS_publish_sks_cancel (psc);
425 * Publish an SBlock on GNUnet.
427 * @param h handle to the file sharing subsystem
428 * @param ns namespace to publish in
429 * @param identifier identifier to use
430 * @param update update identifier to use
431 * @param meta metadata to use
432 * @param uri URI to refer to in the SBlock
433 * @param bo block options
434 * @param options publication options
435 * @param cont continuation
436 * @param cont_cls closure for cont
437 * @return NULL on error ('cont' will still be called)
439 struct GNUNET_FS_PublishSksContext *
440 GNUNET_FS_publish_sks (struct GNUNET_FS_Handle *h,
441 const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns,
442 const char *identifier, const char *update,
443 const struct GNUNET_CONTAINER_MetaData *meta,
444 const struct GNUNET_FS_Uri *uri,
445 const struct GNUNET_FS_BlockOptions *bo,
446 enum GNUNET_FS_PublishOptions options,
447 GNUNET_FS_PublishContinuation cont, void *cont_cls)
449 struct GNUNET_FS_PublishSksContext *psc;
450 struct GNUNET_FS_Uri *sks_uri;
452 sks_uri = GNUNET_new (struct GNUNET_FS_Uri);
453 sks_uri->type = GNUNET_FS_URI_SKS;
454 sks_uri->data.sks.identifier = GNUNET_strdup (identifier);
455 GNUNET_CRYPTO_ecdsa_key_get_public (ns,
456 &sks_uri->data.sks.ns);
458 psc = GNUNET_new (struct GNUNET_FS_PublishSksContext);
462 psc->cont_cls = cont_cls;
464 if (0 == (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
466 psc->dsh = GNUNET_DATASTORE_connect (h->cfg);
467 if (NULL == psc->dsh)
469 sks_publish_cont (psc,
470 _("Failed to connect to datastore."));
476 psc->nsn = GNUNET_new (struct NamespaceUpdateNode);
477 psc->nsn->id = GNUNET_strdup (identifier);
478 psc->nsn->update = GNUNET_strdup (update);
479 psc->nsn->md = GNUNET_CONTAINER_meta_data_duplicate (meta);
480 psc->nsn->uri = GNUNET_FS_uri_dup (uri);
482 psc->uc = GNUNET_FS_publish_ublock_ (h,
498 * Abort the SKS publishing operation.
500 * @param psc context of the operation to abort.
503 GNUNET_FS_publish_sks_cancel (struct GNUNET_FS_PublishSksContext *psc)
507 GNUNET_FS_publish_ublock_cancel_ (psc->uc);
510 if (NULL != psc->dsh)
512 GNUNET_DATASTORE_disconnect (psc->dsh, GNUNET_NO);
515 GNUNET_FS_uri_destroy (psc->uri);
516 if (NULL != psc->nsn)
518 GNUNET_CONTAINER_meta_data_destroy (psc->nsn->md);
519 GNUNET_FS_uri_destroy (psc->nsn->uri);
520 GNUNET_free (psc->nsn->id);
521 GNUNET_free (psc->nsn->update);
522 GNUNET_free (psc->nsn);
529 * Closure for 'process_update_node'.
531 struct ProcessUpdateClosure
534 * Function to call for each node.
536 GNUNET_FS_IdentifierProcessor ip;
546 * Call the iterator in the closure for each node.
548 * @param cls closure (of type 'struct ProcessUpdateClosure *')
549 * @param key current key code
550 * @param value value in the hash map (of type 'struct NamespaceUpdateNode *')
551 * @return GNUNET_YES if we should continue to
556 process_update_node (void *cls,
557 const struct GNUNET_HashCode *key,
560 struct ProcessUpdateClosure *pc = cls;
561 struct NamespaceUpdateNode *nsn = value;
573 * Closure for 'find_trees'.
575 struct FindTreeClosure
578 * UIG we are operating on.
580 struct GNUNET_FS_UpdateInformationGraph *uig;
583 * Array with 'head's of TREEs.
585 struct NamespaceUpdateNode **tree_array;
588 * Size of 'tree_array'
590 unsigned int tree_array_size;
593 * Current generational ID used.
598 * Identifier for the current TREE, or UINT_MAX for none yet.
605 * Find all nodes reachable from the current node (including the
606 * current node itself). If they are in no tree, add them to the
607 * current one. If they are the head of another tree, merge the
608 * trees. If they are in the middle of another tree, let them be.
609 * We can tell that a node is already in an tree by checking if
610 * its 'nug' field is set to the current 'nug' value. It is the
611 * head of an tree if it is in the 'tree_array' under its respective
614 * In short, we're trying to find the smallest number of tree to
615 * cover a directed graph.
617 * @param cls closure (of type 'struct FindTreeClosure')
618 * @param key current key code
619 * @param value value in the hash map
620 * @return GNUNET_YES if we should continue to
625 find_trees (void *cls,
626 const struct GNUNET_HashCode *key,
629 struct FindTreeClosure *fc = cls;
630 struct NamespaceUpdateNode *nsn = value;
631 struct GNUNET_HashCode hc;
633 if (nsn->nug == fc->nug)
635 if (UINT_MAX == nsn->tree_id)
636 return GNUNET_YES; /* circular */
637 GNUNET_assert (nsn->tree_id < fc->tree_array_size);
638 if (fc->tree_array[nsn->tree_id] != nsn)
639 return GNUNET_YES; /* part of "another" (directed) TREE,
640 * and not root of it, end trace */
641 if (nsn->tree_id == fc->id)
642 return GNUNET_YES; /* that's our own root (can this be?) */
643 /* merge existing TREE, we have a root for both */
644 fc->tree_array[nsn->tree_id] = NULL;
645 if (UINT_MAX == fc->id)
646 fc->id = nsn->tree_id; /* take over ID */
651 nsn->tree_id = UINT_MAX; /* mark as undef */
653 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
654 GNUNET_CONTAINER_multihashmap_get_multiple (fc->uig->update_map, &hc,
662 * List all of the identifiers in the namespace for which we could
663 * produce an update. Namespace updates form a graph where each node
664 * has a name. Each node can have any number of URI/meta-data entries
665 * which can each be linked to other nodes. Cycles are possible.
667 * Calling this function with "next_id" NULL will cause the library to
668 * call "ip" with a root for each strongly connected component of the
669 * graph (a root being a node from which all other nodes in the Tree
672 * Calling this function with "next_id" being the name of a node will
673 * cause the library to call "ip" with all children of the node. Note
674 * that cycles within the final tree are possible (including self-loops).
675 * I know, odd definition of a tree, but the GUI will display an actual
676 * tree (GtkTreeView), so that's what counts for the term here.
678 * @param h fs handle to use
679 * @param ns namespace to inspect for updateable content
680 * @param next_id ID to look for; use NULL to look for tree roots
681 * @param ip function to call on each updateable identifier
682 * @param ip_cls closure for ip
685 GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Handle *h,
686 const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns,
688 GNUNET_FS_IdentifierProcessor ip,
693 struct GNUNET_HashCode hc;
694 struct NamespaceUpdateNode *nsn;
695 struct ProcessUpdateClosure pc;
696 struct FindTreeClosure fc;
697 struct GNUNET_FS_UpdateInformationGraph *uig;
699 uig = read_update_information_graph (h, ns);
700 if (NULL == uig->update_nodes)
702 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
703 "No updateable nodes found for ID `%s'\n", next_id);
704 free_update_information_graph (uig);
705 return; /* no nodes */
708 GNUNET_CONTAINER_multihashmap_create (2 +
709 3 * uig->update_node_count /
712 for (i = 0; i < uig->update_node_count; i++)
714 nsn = uig->update_nodes[i];
715 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
716 GNUNET_CONTAINER_multihashmap_put (uig->update_map, &hc, nsn,
717 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
721 GNUNET_CRYPTO_hash (next_id, strlen (next_id), &hc);
724 GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
725 &process_update_node, &pc);
726 free_update_information_graph (uig);
729 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
730 "Calculating TREEs to find roots of update trees\n");
731 /* Find heads of TREEs in update graph */
732 nug = ++uig->nug_gen;
733 fc.tree_array = NULL;
734 fc.tree_array_size = 0;
736 for (i = 0; i < uig->update_node_count; i++)
738 nsn = uig->update_nodes[i];
741 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
743 continue; /* already placed in TREE */
745 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
747 nsn->tree_id = UINT_MAX;
751 GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
753 if (UINT_MAX == fc.id)
756 for (fc.id = 0; fc.id < fc.tree_array_size; fc.id++)
758 if (NULL == fc.tree_array[fc.id])
760 fc.tree_array[fc.id] = nsn;
761 nsn->tree_id = fc.id;
765 if (fc.id == fc.tree_array_size)
767 GNUNET_array_append (fc.tree_array, fc.tree_array_size, nsn);
768 nsn->tree_id = fc.id;
770 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
771 "Starting new TREE %u with node `%s'\n", nsn->tree_id,
773 /* put all nodes with same identifier into this TREE */
774 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
775 fc.id = nsn->tree_id;
778 GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
783 /* make head of TREE "id" */
784 fc.tree_array[fc.id] = nsn;
785 nsn->tree_id = fc.id;
787 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
788 "TREE of node `%s' is %u\n", nsn->id,
791 for (i = 0; i < fc.tree_array_size; i++)
793 nsn = fc.tree_array[i];
796 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Root of TREE %u is node `%s'\n", i,
798 ip (ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
801 GNUNET_array_grow (fc.tree_array, fc.tree_array_size, 0);
802 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Done processing TREEs\n");
803 free_update_information_graph (uig);
807 /* end of fs_namespace.c */