2 This file is part of GNUnet
3 (C) 2003-2013 Christian Grothoff (and other contributing authors)
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., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
22 * @file fs/fs_namespace.c
23 * @brief publishing to namespaces, and tracking updateable entries
24 * @author Christian Grothoff
27 #include "gnunet_constants.h"
28 #include "gnunet_signatures.h"
29 #include "gnunet_util_lib.h"
30 #include "gnunet_fs_service.h"
32 #include "fs_publish_ublock.h"
36 * Information about an (updateable) node in the
39 struct NamespaceUpdateNode
42 * Identifier for this node.
47 * Identifier of children of this node.
52 * Metadata for this entry.
54 struct GNUNET_CONTAINER_MetaData *md;
57 * URI of this entry in the namespace.
59 struct GNUNET_FS_Uri *uri;
62 * Namespace update generation ID. Used to ensure
63 * freshness of the tree_id.
68 * TREE this entry belongs to (if nug is current).
76 * Handle to update information for a namespace.
78 struct GNUNET_FS_UpdateInformationGraph
82 * Handle to the FS service context.
84 struct GNUNET_FS_Handle *h;
87 * Array with information about nodes in the namespace.
89 struct NamespaceUpdateNode **update_nodes;
92 * Private key for the namespace.
94 struct GNUNET_CRYPTO_EccPrivateKey ns;
97 * Hash map mapping identifiers of update nodes
98 * to the update nodes (initialized on-demand).
100 struct GNUNET_CONTAINER_MultiHashMap *update_map;
103 * Size of the update nodes array.
105 unsigned int update_node_count;
113 * Generator for unique nug numbers.
115 unsigned int nug_gen;
120 * Return the name of the directory in which we store
121 * the update information graph for the given local namespace.
123 * @param ns namespace handle
124 * @return NULL on error, otherwise the name of the directory
127 get_update_information_directory (struct GNUNET_FS_Handle *h,
128 const struct GNUNET_CRYPTO_EccPrivateKey *ns)
132 struct GNUNET_CRYPTO_EccPublicKey pub;
133 struct GNUNET_CRYPTO_ShortHashCode hc;
134 struct GNUNET_CRYPTO_ShortHashAsciiEncoded enc;
137 GNUNET_CONFIGURATION_get_value_filename (h->cfg, "FS", "UPDATE_DIR",
140 GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
144 GNUNET_CRYPTO_ecc_key_get_public (ns, &pub);
145 GNUNET_CRYPTO_short_hash (&pub, sizeof (pub), &hc);
146 GNUNET_CRYPTO_short_hash_to_enc (&hc,
148 GNUNET_asprintf (&ret, "%s%s%s",
151 (const char *) enc.short_encoding);
158 * Release memory occupied by UIG datastructure.
160 * @param uig data structure to free
163 free_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
166 struct NamespaceUpdateNode *nsn;
168 for (i = 0; i < uig->update_node_count; i++)
170 nsn = uig->update_nodes[i];
171 GNUNET_CONTAINER_meta_data_destroy (nsn->md);
172 GNUNET_FS_uri_destroy (nsn->uri);
173 GNUNET_free (nsn->id);
174 GNUNET_free (nsn->update);
177 GNUNET_array_grow (uig->update_nodes, uig->update_node_count,
179 if (NULL != uig->update_map)
180 GNUNET_CONTAINER_multihashmap_destroy (uig->update_map);
186 * Write the namespace update node graph to a file.
188 * @param ns namespace to dump
191 write_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
194 struct GNUNET_BIO_WriteHandle *wh;
196 struct NamespaceUpdateNode *n;
199 fn = get_update_information_directory (uig->h,
201 wh = GNUNET_BIO_write_open (fn);
204 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
205 _("Failed to open `%s' for writing: %s\n"), STRERROR (errno));
209 if (GNUNET_OK != GNUNET_BIO_write_int32 (wh, uig->update_node_count))
211 for (i = 0; i < uig->update_node_count; i++)
213 n = uig->update_nodes[i];
214 uris = GNUNET_FS_uri_to_string (n->uri);
215 if ((GNUNET_OK != GNUNET_BIO_write_string (wh, n->id)) ||
216 (GNUNET_OK != GNUNET_BIO_write_meta_data (wh, n->md)) ||
217 (GNUNET_OK != GNUNET_BIO_write_string (wh, n->update)) ||
218 (GNUNET_OK != GNUNET_BIO_write_string (wh, uris)))
226 if (GNUNET_OK != GNUNET_BIO_write_close (wh))
227 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to write `%s': %s\n"),
234 * Read the namespace update node graph from a file.
236 * @param h FS handle to use
237 * @param ns namespace to read
238 * @return update graph, never NULL
240 static struct GNUNET_FS_UpdateInformationGraph *
241 read_update_information_graph (struct GNUNET_FS_Handle *h,
242 const struct GNUNET_CRYPTO_EccPrivateKey *ns)
244 struct GNUNET_FS_UpdateInformationGraph *uig;
246 struct GNUNET_BIO_ReadHandle *rh;
248 struct NamespaceUpdateNode *n;
253 uig = GNUNET_new (struct GNUNET_FS_UpdateInformationGraph);
256 fn = get_update_information_directory (h, ns);
257 if (GNUNET_YES != GNUNET_DISK_file_test (fn))
262 rh = GNUNET_BIO_read_open (fn);
268 if (GNUNET_OK != GNUNET_BIO_read_int32 (rh, &count))
273 if (count > 1024 * 1024)
280 GNUNET_break (GNUNET_OK == GNUNET_BIO_read_close (rh, NULL));
285 GNUNET_malloc (count * sizeof (struct NamespaceUpdateNode *));
287 for (i = 0; i < count; i++)
289 n = GNUNET_new (struct NamespaceUpdateNode);
290 if ((GNUNET_OK != GNUNET_BIO_read_string (rh, "identifier", &n->id, 1024))
291 || (GNUNET_OK != GNUNET_BIO_read_meta_data (rh, "meta", &n->md)) ||
293 GNUNET_BIO_read_string (rh, "update-id", &n->update, 1024)) ||
294 (GNUNET_OK != GNUNET_BIO_read_string (rh, "uri", &uris, 1024 * 2)))
297 GNUNET_free_non_null (n->id);
298 GNUNET_free_non_null (n->update);
300 GNUNET_CONTAINER_meta_data_destroy (n->md);
304 n->uri = GNUNET_FS_uri_parse (uris, &emsg);
311 GNUNET_free_non_null (n->update);
312 GNUNET_CONTAINER_meta_data_destroy (n->md);
316 uig->update_nodes[i] = n;
318 uig->update_node_count = i;
319 if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
321 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to read `%s': %s\n"),
327 if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
329 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to read `%s': %s\n"),
339 * Context for the SKS publication.
341 struct GNUNET_FS_PublishSksContext
345 * URI of the new entry in the namespace.
347 struct GNUNET_FS_Uri *uri;
350 * Namespace update node to add to namespace on success (or to be
351 * deleted if publishing failed).
353 struct NamespaceUpdateNode *nsn;
356 * Namespace we're publishing to.
358 struct GNUNET_CRYPTO_EccPrivateKey ns;
361 * Handle to the datastore.
363 struct GNUNET_DATASTORE_Handle *dsh;
368 struct GNUNET_FS_Handle *h;
371 * Function to call once we're done.
373 GNUNET_FS_PublishContinuation cont;
381 * Handle for our UBlock operation request.
383 struct GNUNET_FS_PublishUblockContext *uc;
388 * Function called by the UBlock construction with
389 * the result from the PUT (UBlock) request.
391 * @param cls closure of type "struct GNUNET_FS_PublishSksContext*"
392 * @param msg error message (or NULL)
395 sks_publish_cont (void *cls,
398 struct GNUNET_FS_PublishSksContext *psc = cls;
399 struct GNUNET_FS_UpdateInformationGraph *uig;
404 if (NULL != psc->cont)
405 psc->cont (psc->cont_cls, NULL, msg);
406 GNUNET_FS_publish_sks_cancel (psc);
409 if (NULL != psc->nsn)
411 /* FIXME: this can be done much more
412 * efficiently by simply appending to the
413 * file and overwriting the 4-byte header */
414 uig = read_update_information_graph (psc->h,
416 GNUNET_array_append (uig->update_nodes,
417 uig->update_node_count,
420 write_update_information_graph (uig);
421 free_update_information_graph (uig);
423 if (NULL != psc->cont)
424 psc->cont (psc->cont_cls, psc->uri, NULL);
425 GNUNET_FS_publish_sks_cancel (psc);
430 * Publish an SBlock on GNUnet.
432 * @param h handle to the file sharing subsystem
433 * @param ns namespace to publish in
434 * @param identifier identifier to use
435 * @param update update identifier to use
436 * @param meta metadata to use
437 * @param uri URI to refer to in the SBlock
438 * @param bo block options
439 * @param options publication options
440 * @param cont continuation
441 * @param cont_cls closure for cont
442 * @return NULL on error ('cont' will still be called)
444 struct GNUNET_FS_PublishSksContext *
445 GNUNET_FS_publish_sks (struct GNUNET_FS_Handle *h,
446 const struct GNUNET_CRYPTO_EccPrivateKey *ns,
447 const char *identifier, const char *update,
448 const struct GNUNET_CONTAINER_MetaData *meta,
449 const struct GNUNET_FS_Uri *uri,
450 const struct GNUNET_FS_BlockOptions *bo,
451 enum GNUNET_FS_PublishOptions options,
452 GNUNET_FS_PublishContinuation cont, void *cont_cls)
454 struct GNUNET_FS_PublishSksContext *psc;
455 struct GNUNET_FS_Uri *sks_uri;
457 sks_uri = GNUNET_new (struct GNUNET_FS_Uri);
458 sks_uri->type = GNUNET_FS_URI_SKS;
459 sks_uri->data.sks.identifier = GNUNET_strdup (identifier);
460 GNUNET_CRYPTO_ecc_key_get_public (ns,
461 &sks_uri->data.sks.ns);
463 psc = GNUNET_new (struct GNUNET_FS_PublishSksContext);
467 psc->cont_cls = cont_cls;
469 if (0 == (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
471 psc->dsh = GNUNET_DATASTORE_connect (h->cfg);
472 if (NULL == psc->dsh)
474 sks_publish_cont (psc,
475 _("Failed to connect to datastore."));
481 psc->nsn = GNUNET_new (struct NamespaceUpdateNode);
482 psc->nsn->id = GNUNET_strdup (identifier);
483 psc->nsn->update = GNUNET_strdup (update);
484 psc->nsn->md = GNUNET_CONTAINER_meta_data_duplicate (meta);
485 psc->nsn->uri = GNUNET_FS_uri_dup (uri);
487 psc->uc = GNUNET_FS_publish_ublock_ (h,
503 * Abort the SKS publishing operation.
505 * @param psc context of the operation to abort.
508 GNUNET_FS_publish_sks_cancel (struct GNUNET_FS_PublishSksContext *psc)
512 GNUNET_FS_publish_ublock_cancel_ (psc->uc);
515 if (NULL != psc->dsh)
517 GNUNET_DATASTORE_disconnect (psc->dsh, GNUNET_NO);
520 GNUNET_FS_uri_destroy (psc->uri);
521 if (NULL != psc->nsn)
523 GNUNET_CONTAINER_meta_data_destroy (psc->nsn->md);
524 GNUNET_FS_uri_destroy (psc->nsn->uri);
525 GNUNET_free (psc->nsn->id);
526 GNUNET_free (psc->nsn->update);
527 GNUNET_free (psc->nsn);
534 * Closure for 'process_update_node'.
536 struct ProcessUpdateClosure
539 * Function to call for each node.
541 GNUNET_FS_IdentifierProcessor ip;
551 * Call the iterator in the closure for each node.
553 * @param cls closure (of type 'struct ProcessUpdateClosure *')
554 * @param key current key code
555 * @param value value in the hash map (of type 'struct NamespaceUpdateNode *')
556 * @return GNUNET_YES if we should continue to
561 process_update_node (void *cls,
562 const struct GNUNET_HashCode *key,
565 struct ProcessUpdateClosure *pc = cls;
566 struct NamespaceUpdateNode *nsn = value;
578 * Closure for 'find_trees'.
580 struct FindTreeClosure
583 * UIG we are operating on.
585 struct GNUNET_FS_UpdateInformationGraph *uig;
588 * Array with 'head's of TREEs.
590 struct NamespaceUpdateNode **tree_array;
593 * Size of 'tree_array'
595 unsigned int tree_array_size;
598 * Current generational ID used.
603 * Identifier for the current TREE, or UINT_MAX for none yet.
610 * Find all nodes reachable from the current node (including the
611 * current node itself). If they are in no tree, add them to the
612 * current one. If they are the head of another tree, merge the
613 * trees. If they are in the middle of another tree, let them be.
614 * We can tell that a node is already in an tree by checking if
615 * its 'nug' field is set to the current 'nug' value. It is the
616 * head of an tree if it is in the 'tree_array' under its respective
619 * In short, we're trying to find the smallest number of tree to
620 * cover a directed graph.
622 * @param cls closure (of type 'struct FindTreeClosure')
623 * @param key current key code
624 * @param value value in the hash map
625 * @return GNUNET_YES if we should continue to
630 find_trees (void *cls,
631 const struct GNUNET_HashCode *key,
634 struct FindTreeClosure *fc = cls;
635 struct NamespaceUpdateNode *nsn = value;
636 struct GNUNET_HashCode hc;
638 if (nsn->nug == fc->nug)
640 if (UINT_MAX == nsn->tree_id)
641 return GNUNET_YES; /* circular */
642 GNUNET_assert (nsn->tree_id < fc->tree_array_size);
643 if (fc->tree_array[nsn->tree_id] != nsn)
644 return GNUNET_YES; /* part of "another" (directed) TREE,
645 * and not root of it, end trace */
646 if (nsn->tree_id == fc->id)
647 return GNUNET_YES; /* that's our own root (can this be?) */
648 /* merge existing TREE, we have a root for both */
649 fc->tree_array[nsn->tree_id] = NULL;
650 if (UINT_MAX == fc->id)
651 fc->id = nsn->tree_id; /* take over ID */
656 nsn->tree_id = UINT_MAX; /* mark as undef */
658 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
659 GNUNET_CONTAINER_multihashmap_get_multiple (fc->uig->update_map, &hc,
667 * List all of the identifiers in the namespace for which we could
668 * produce an update. Namespace updates form a graph where each node
669 * has a name. Each node can have any number of URI/meta-data entries
670 * which can each be linked to other nodes. Cycles are possible.
672 * Calling this function with "next_id" NULL will cause the library to
673 * call "ip" with a root for each strongly connected component of the
674 * graph (a root being a node from which all other nodes in the Tree
677 * Calling this function with "next_id" being the name of a node will
678 * cause the library to call "ip" with all children of the node. Note
679 * that cycles within the final tree are possible (including self-loops).
680 * I know, odd definition of a tree, but the GUI will display an actual
681 * tree (GtkTreeView), so that's what counts for the term here.
683 * @param h fs handle to use
684 * @param ns namespace to inspect for updateable content
685 * @param next_id ID to look for; use NULL to look for tree roots
686 * @param ip function to call on each updateable identifier
687 * @param ip_cls closure for ip
690 GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Handle *h,
691 const struct GNUNET_CRYPTO_EccPrivateKey *ns,
693 GNUNET_FS_IdentifierProcessor ip,
698 struct GNUNET_HashCode hc;
699 struct NamespaceUpdateNode *nsn;
700 struct ProcessUpdateClosure pc;
701 struct FindTreeClosure fc;
702 struct GNUNET_FS_UpdateInformationGraph *uig;
704 uig = read_update_information_graph (h, ns);
705 if (NULL == uig->update_nodes)
707 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
708 "No updateable nodes found for ID `%s'\n", next_id);
709 free_update_information_graph (uig);
710 return; /* no nodes */
713 GNUNET_CONTAINER_multihashmap_create (2 +
714 3 * uig->update_node_count /
717 for (i = 0; i < uig->update_node_count; i++)
719 nsn = uig->update_nodes[i];
720 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
721 GNUNET_CONTAINER_multihashmap_put (uig->update_map, &hc, nsn,
722 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
726 GNUNET_CRYPTO_hash (next_id, strlen (next_id), &hc);
729 GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
730 &process_update_node, &pc);
731 free_update_information_graph (uig);
734 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
735 "Calculating TREEs to find roots of update trees\n");
736 /* Find heads of TREEs in update graph */
737 nug = ++uig->nug_gen;
738 fc.tree_array = NULL;
739 fc.tree_array_size = 0;
741 for (i = 0; i < uig->update_node_count; i++)
743 nsn = uig->update_nodes[i];
746 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
748 continue; /* already placed in TREE */
750 GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
752 nsn->tree_id = UINT_MAX;
756 GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
758 if (UINT_MAX == fc.id)
761 for (fc.id = 0; fc.id < fc.tree_array_size; fc.id++)
763 if (NULL == fc.tree_array[fc.id])
765 fc.tree_array[fc.id] = nsn;
766 nsn->tree_id = fc.id;
770 if (fc.id == fc.tree_array_size)
772 GNUNET_array_append (fc.tree_array, fc.tree_array_size, nsn);
773 nsn->tree_id = fc.id;
775 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
776 "Starting new TREE %u with node `%s'\n", nsn->tree_id,
778 /* put all nodes with same identifier into this TREE */
779 GNUNET_CRYPTO_hash (nsn->id, strlen (nsn->id), &hc);
780 fc.id = nsn->tree_id;
783 GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
788 /* make head of TREE "id" */
789 fc.tree_array[fc.id] = nsn;
790 nsn->tree_id = fc.id;
792 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
793 "TREE of node `%s' is %u\n", nsn->id,
796 for (i = 0; i < fc.tree_array_size; i++)
798 nsn = fc.tree_array[i];
801 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Root of TREE %u is node `%s'\n", i,
803 ip (ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
806 GNUNET_array_grow (fc.tree_array, fc.tree_array_size, 0);
807 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Done processing TREEs\n");
808 free_update_information_graph (uig);
812 /* end of fs_namespace.c */