2 This file is part of GNUnet
3 (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 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 create and destroy namespaces
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"
33 #define DEBUG_NAMESPACE GNUNET_NO
36 * Return the name of the directory in which we store
37 * our local namespaces (or rather, their public keys).
39 * @param h global fs handle
40 * @return NULL on error, otherwise the name of the directory
43 get_namespace_directory (struct GNUNET_FS_Handle *h)
48 GNUNET_CONFIGURATION_get_value_filename (h->cfg,
53 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
54 _("Configuration fails to specify `%s' in section `%s'\n"),
64 * Return the name of the directory in which we store
65 * the update information graph for the given local namespace.
67 * @param ns namespace handle
68 * @return NULL on error, otherwise the name of the directory
71 get_update_information_directory (struct GNUNET_FS_Namespace *ns)
77 GNUNET_CONFIGURATION_get_value_filename (ns->h->cfg,
82 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
83 _("Configuration fails to specify `%s' in section `%s'\n"),
88 GNUNET_asprintf (&ret,
99 * Write the namespace update node graph to a file.
101 * @param ns namespace to dump
104 write_update_information_graph (struct GNUNET_FS_Namespace *ns)
107 struct GNUNET_BIO_WriteHandle *wh;
109 struct NamespaceUpdateNode *n;
112 fn = get_update_information_directory (ns);
113 wh = GNUNET_BIO_write_open (fn);
116 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
117 _("Failed to open `%s' for writing: %s\n"),
123 GNUNET_BIO_write_int32 (wh, ns->update_node_count))
125 for (i=0;i<ns->update_node_count;i++)
127 n = ns->update_nodes[i];
128 uris = GNUNET_FS_uri_to_string (n->uri);
130 GNUNET_BIO_write_string (wh, n->id)) ||
132 GNUNET_BIO_write_meta_data (wh, n->md)) ||
134 GNUNET_BIO_write_string (wh, n->update)) ||
136 GNUNET_BIO_write_string (wh, uris)) )
144 if (GNUNET_OK != GNUNET_BIO_write_close (wh))
145 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
146 _("Failed to write `%s': %s\n"),
153 * Read the namespace update node graph from a file.
155 * @param ns namespace to read
158 read_update_information_graph (struct GNUNET_FS_Namespace *ns)
161 struct GNUNET_BIO_ReadHandle *rh;
163 struct NamespaceUpdateNode *n;
168 fn = get_update_information_directory (ns);
170 GNUNET_DISK_file_test (fn))
175 rh = GNUNET_BIO_read_open (fn);
182 GNUNET_BIO_read_int32 (rh, &count))
187 if (count > 1024 * 1024)
194 GNUNET_break (GNUNET_OK == GNUNET_BIO_read_close (rh, NULL));
198 ns->update_nodes = GNUNET_malloc (count * sizeof (struct NamespaceUpdateNode*));
200 for (i=0;i<count;i++)
202 n = GNUNET_malloc (sizeof (struct NamespaceUpdateNode));
204 GNUNET_BIO_read_string (rh, "identifier", &n->id, 1024)) ||
206 GNUNET_BIO_read_meta_data (rh, "meta", &n->md)) ||
208 GNUNET_BIO_read_string (rh, "update-id", &n->update, 1024)) ||
210 GNUNET_BIO_read_string (rh, "uri", &uris, 1024 * 2)) )
213 GNUNET_free_non_null (n->id);
214 GNUNET_free_non_null (n->update);
216 GNUNET_CONTAINER_meta_data_destroy (n->md);
220 n->uri = GNUNET_FS_uri_parse (uris, &emsg);
227 GNUNET_free_non_null (n->update);
228 GNUNET_CONTAINER_meta_data_destroy (n->md);
232 ns->update_nodes[i] = n;
234 ns->update_node_count = i;
236 if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
238 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
239 _("Failed to write `%s': %s\n"),
248 * Context for advertising a namespace.
250 struct AdvertisementContext
253 * Function to call with the result.
255 GNUNET_FS_PublishContinuation cont;
265 struct GNUNET_DATASTORE_Handle *dsh;
270 struct GNUNET_FS_Uri *ksk_uri;
278 * NBlock to sign and store.
285 struct GNUNET_FS_Namespace *ns;
290 struct GNUNET_FS_BlockOptions bo;
293 * Number of bytes of plaintext.
298 * Current keyword offset.
305 * Disconnect from the datastore.
307 * @param cls datastore handle
308 * @param tc scheduler context
311 do_disconnect (void *cls,
312 const struct GNUNET_SCHEDULER_TaskContext *tc)
314 struct GNUNET_DATASTORE_Handle *dsh = cls;
316 GNUNET_DATASTORE_disconnect (dsh,
322 * Continuation called to notify client about result of the
325 * @param cls closure (our struct AdvertismentContext)
326 * @param success GNUNET_SYSERR on failure
327 * @param msg NULL on success, otherwise an error message
330 advertisement_cont (void *cls,
334 struct AdvertisementContext *ac = cls;
337 GNUNET_HashCode query;
338 struct GNUNET_CRYPTO_AesSessionKey skey;
339 struct GNUNET_CRYPTO_AesInitializationVector iv;
340 struct GNUNET_CRYPTO_RsaPrivateKey *pk;
342 if (GNUNET_OK != success)
345 GNUNET_SCHEDULER_add_continuation (&do_disconnect,
347 GNUNET_SCHEDULER_REASON_PREREQ_DONE);
351 msg = _("Unknown error");
353 if (ac->cont != NULL)
354 ac->cont (ac->cont_cls, NULL, msg);
355 GNUNET_FS_uri_destroy (ac->ksk_uri);
356 GNUNET_free (ac->pt);
357 GNUNET_free (ac->nb);
358 GNUNET_FS_namespace_delete (ac->ns, GNUNET_NO);
362 if (ac->pos == ac->ksk_uri->data.ksk.keywordCount)
365 GNUNET_SCHEDULER_add_continuation (&do_disconnect,
367 GNUNET_SCHEDULER_REASON_PREREQ_DONE);
368 if (ac->cont != NULL)
369 ac->cont (ac->cont_cls, ac->ksk_uri, NULL);
370 GNUNET_FS_uri_destroy (ac->ksk_uri);
371 GNUNET_free (ac->pt);
372 GNUNET_free (ac->nb);
373 GNUNET_FS_namespace_delete (ac->ns, GNUNET_NO);
377 keyword = ac->ksk_uri->data.ksk.keywords[ac->pos++];
378 /* first character of keyword indicates if it is
379 mandatory or not -- ignore for hashing */
380 GNUNET_CRYPTO_hash (&keyword[1], strlen (&keyword[1]), &key);
381 GNUNET_CRYPTO_hash_to_aes_key (&key, &skey, &iv);
382 GNUNET_CRYPTO_aes_encrypt (ac->pt,
387 GNUNET_break (GNUNET_OK ==
388 GNUNET_CRYPTO_rsa_sign (ac->ns->key,
390 &ac->nb->ns_signature));
391 pk = GNUNET_CRYPTO_rsa_key_create_from_hash (&key);
392 GNUNET_assert (pk != NULL);
393 GNUNET_CRYPTO_rsa_key_get_public (pk, &ac->nb->keyspace);
394 GNUNET_CRYPTO_hash (&ac->nb->keyspace,
395 sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded),
397 GNUNET_break (GNUNET_OK ==
398 GNUNET_CRYPTO_rsa_sign (pk,
399 &ac->nb->ksk_purpose,
400 &ac->nb->ksk_signature));
401 GNUNET_CRYPTO_rsa_key_free (pk);
402 GNUNET_DATASTORE_put (ac->dsh,
403 0 /* no reservation */,
405 ac->pt_size + sizeof (struct NBlock),
407 GNUNET_BLOCK_TYPE_FS_NBLOCK,
408 ac->bo.content_priority,
409 ac->bo.anonymity_level,
410 ac->bo.replication_level,
411 ac->bo.expiration_time,
413 GNUNET_CONSTANTS_SERVICE_TIMEOUT,
420 * Publish an advertismement for a namespace.
422 * @param h handle to the file sharing subsystem
423 * @param ksk_uri keywords to use for advertisment
424 * @param namespace handle for the namespace that should be advertised
425 * @param meta meta-data for the namespace advertisement
426 * @param bo block options
427 * @param rootEntry name of the root of the namespace
428 * @param cont continuation
429 * @param cont_cls closure for cont
432 GNUNET_FS_namespace_advertise (struct GNUNET_FS_Handle *h,
433 struct GNUNET_FS_Uri *ksk_uri,
434 struct GNUNET_FS_Namespace *namespace,
435 const struct GNUNET_CONTAINER_MetaData *meta,
436 const struct GNUNET_FS_BlockOptions *bo,
437 const char *rootEntry,
438 GNUNET_FS_PublishContinuation cont,
446 struct GNUNET_DATASTORE_Handle *dsh;
447 struct AdvertisementContext *ctx;
450 /* create advertisements */
451 mdsize = GNUNET_CONTAINER_meta_data_get_serialized_size (meta);
454 cont (cont_cls, NULL, _("Failed to serialize meta data"));
457 reslen = strlen (rootEntry) + 1;
458 size = mdsize + sizeof (struct NBlock) + reslen;
459 if (size > MAX_NBLOCK_SIZE)
461 size = MAX_NBLOCK_SIZE;
462 mdsize = size - sizeof (struct NBlock) - reslen;
465 pt = GNUNET_malloc (mdsize + reslen);
466 memcpy (pt, rootEntry, reslen);
468 mdsize = GNUNET_CONTAINER_meta_data_serialize (meta,
471 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
476 cont (cont_cls, NULL, _("Failed to serialize meta data"));
479 size = mdsize + sizeof (struct NBlock) + reslen;
480 nb = GNUNET_malloc (size);
481 GNUNET_CRYPTO_rsa_key_get_public (namespace->key,
483 nb->ns_purpose.size = htonl (mdsize + reslen +
484 sizeof (struct GNUNET_CRYPTO_RsaSignaturePurpose) +
485 sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
486 nb->ns_purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_FS_NBLOCK);
487 nb->ksk_purpose.size = htonl (size - sizeof (struct GNUNET_CRYPTO_RsaSignature));
488 nb->ksk_purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_FS_NBLOCK_KSIG);
489 dsh = GNUNET_DATASTORE_connect (h->cfg);
494 cont (cont_cls, NULL, _("Failed to connect to datastore service"));
497 ctx = GNUNET_malloc (sizeof (struct AdvertisementContext));
499 ctx->cont_cls = cont_cls;
501 ctx->ksk_uri = GNUNET_FS_uri_dup (ksk_uri);
504 ctx->pt_size = mdsize + reslen;
508 advertisement_cont (ctx, GNUNET_OK, NULL);
513 * Create a namespace with the given name; if one already
514 * exists, return a handle to the existing namespace.
516 * @param h handle to the file sharing subsystem
517 * @param name name to use for the namespace
518 * @return handle to the namespace, NULL on error
520 struct GNUNET_FS_Namespace *
521 GNUNET_FS_namespace_create (struct GNUNET_FS_Handle *h,
526 struct GNUNET_FS_Namespace *ret;
528 dn = get_namespace_directory (h);
529 GNUNET_asprintf (&fn,
535 ret = GNUNET_malloc (sizeof (struct GNUNET_FS_Namespace));
538 ret->key = GNUNET_CRYPTO_rsa_key_create_from_file (fn);
539 if (ret->key == NULL)
541 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
542 _("Failed to create or read private key for namespace `%s'\n"),
548 ret->name = GNUNET_strdup (name);
555 * Delete a namespace handle. Can be used for a clean shutdown (free
556 * memory) or also to freeze the namespace to prevent further
557 * insertions by anyone.
559 * @param namespace handle to the namespace that should be deleted / freed
560 * @param freeze prevents future insertions; creating a namespace
561 * with the same name again will create a fresh namespace instead
563 * @return GNUNET_OK on success, GNUNET_SYSERR on error
566 GNUNET_FS_namespace_delete (struct GNUNET_FS_Namespace *namespace,
570 struct NamespaceUpdateNode *nsn;
575 if (0 != UNLINK (namespace->filename))
576 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR,
578 namespace->filename);
580 if (0 == namespace->rc)
582 GNUNET_CRYPTO_rsa_key_free (namespace->key);
583 GNUNET_free (namespace->filename);
584 GNUNET_free (namespace->name);
585 for (i=0;i<namespace->update_node_count;i++)
587 nsn = namespace->update_nodes[i];
588 GNUNET_CONTAINER_meta_data_destroy (nsn->md);
589 GNUNET_FS_uri_destroy (nsn->uri);
590 GNUNET_free (nsn->id);
591 GNUNET_free (nsn->update);
594 GNUNET_array_grow (namespace->update_nodes,
595 namespace->update_node_count,
597 if (namespace->update_map != NULL)
598 GNUNET_CONTAINER_multihashmap_destroy (namespace->update_map);
599 GNUNET_free (namespace);
606 * Context for the 'process_namespace' callback.
607 * Specifies a function to call on each namespace.
609 struct ProcessNamespaceContext
614 GNUNET_FS_NamespaceInfoProcessor cb;
624 * Function called with a filename of a namespace. Reads the key and
625 * calls the callback.
627 * @param cls closure (struct ProcessNamespaceContext)
628 * @param filename complete filename (absolute path)
629 * @return GNUNET_OK to continue to iterate,
630 * GNUNET_SYSERR to abort iteration with error!
633 process_namespace (void *cls,
634 const char *filename)
636 struct ProcessNamespaceContext *pnc = cls;
637 struct GNUNET_CRYPTO_RsaPrivateKey *key;
638 struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded pk;
643 key = GNUNET_CRYPTO_rsa_key_create_from_file (filename);
646 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
647 _("Failed to read namespace private key file `%s', deleting it!\n"),
649 if (0 != UNLINK (filename))
650 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING,
655 GNUNET_CRYPTO_rsa_key_get_public (key, &pk);
656 GNUNET_CRYPTO_rsa_key_free (key);
657 GNUNET_CRYPTO_hash (&pk, sizeof(pk), &id);
659 while (NULL != (t = strstr (name, DIR_SEPARATOR_STR)))
661 pnc->cb (pnc->cb_cls,
669 * Build a list of all available local (!) namespaces The returned
670 * names are only the nicknames since we only iterate over the local
673 * @param h handle to the file sharing subsystem
674 * @param cb function to call on each known namespace
675 * @param cb_cls closure for cb
678 GNUNET_FS_namespace_list (struct GNUNET_FS_Handle *h,
679 GNUNET_FS_NamespaceInfoProcessor cb,
683 struct ProcessNamespaceContext ctx;
685 dn = get_namespace_directory (h);
690 GNUNET_DISK_directory_scan (dn,
700 * Context for the SKS publication.
702 struct PublishSksContext
706 * URI of the new entry in the namespace.
708 struct GNUNET_FS_Uri *uri;
711 * Namespace update node to add to namespace on success (or to be
712 * deleted if publishing failed).
714 struct NamespaceUpdateNode *nsn;
717 * Namespace we're publishing to.
719 struct GNUNET_FS_Namespace *namespace;
722 * Handle to the datastore.
724 struct GNUNET_DATASTORE_Handle *dsh;
727 * Function to call once we're done.
729 GNUNET_FS_PublishContinuation cont;
740 * Function called by the datastore API with
741 * the result from the PUT (SBlock) request.
743 * @param cls closure of type "struct PublishSksContext*"
744 * @param success GNUNET_OK on success
745 * @param msg error message (or NULL)
748 sb_put_cont (void *cls,
752 struct PublishSksContext *psc = cls;
755 if (NULL != psc->dsh)
757 GNUNET_DATASTORE_disconnect (psc->dsh, GNUNET_NO);
760 if (GNUNET_OK != success)
762 if (psc->cont != NULL)
763 psc->cont (psc->cont_cls,
769 if (psc->nsn != NULL)
771 /* FIXME: this can be done much more
772 efficiently by simply appending to the
773 file and overwriting the 4-byte header */
774 if (psc->namespace->update_nodes == NULL)
775 read_update_information_graph (psc->namespace);
776 GNUNET_array_append (psc->namespace->update_nodes,
777 psc->namespace->update_node_count,
779 if (psc->namespace->update_map != NULL)
781 GNUNET_CRYPTO_hash (psc->nsn->id,
782 strlen (psc->nsn->id),
784 GNUNET_CONTAINER_multihashmap_put (psc->namespace->update_map,
787 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
790 write_update_information_graph (psc->namespace);
792 if (psc->cont != NULL)
793 psc->cont (psc->cont_cls,
797 GNUNET_FS_namespace_delete (psc->namespace,
799 GNUNET_FS_uri_destroy (psc->uri);
800 if (psc->nsn != NULL)
802 GNUNET_CONTAINER_meta_data_destroy (psc->nsn->md);
803 GNUNET_FS_uri_destroy (psc->nsn->uri);
804 GNUNET_free (psc->nsn->id);
805 GNUNET_free (psc->nsn->update);
806 GNUNET_free (psc->nsn);
813 * Publish an SBlock on GNUnet.
815 * @param h handle to the file sharing subsystem
816 * @param namespace namespace to publish in
817 * @param identifier identifier to use
818 * @param update update identifier to use
819 * @param meta metadata to use
820 * @param uri URI to refer to in the SBlock
821 * @param bo block options
822 * @param options publication options
823 * @param cont continuation
824 * @param cont_cls closure for cont
827 GNUNET_FS_publish_sks (struct GNUNET_FS_Handle *h,
828 struct GNUNET_FS_Namespace *namespace,
829 const char *identifier,
831 const struct GNUNET_CONTAINER_MetaData *meta,
832 const struct GNUNET_FS_Uri *uri,
833 const struct GNUNET_FS_BlockOptions *bo,
834 enum GNUNET_FS_PublishOptions options,
835 GNUNET_FS_PublishContinuation cont,
838 struct PublishSksContext *psc;
839 struct GNUNET_CRYPTO_AesSessionKey sk;
840 struct GNUNET_CRYPTO_AesInitializationVector iv;
841 struct GNUNET_FS_Uri *sks_uri;
849 struct SBlock *sb_enc;
851 struct GNUNET_CONTAINER_MetaData *mmeta;
852 GNUNET_HashCode key; /* hash of thisId = key */
853 GNUNET_HashCode id; /* hash of hc = identifier */
854 GNUNET_HashCode query; /* id ^ nsid = DB query */
857 mmeta = GNUNET_CONTAINER_meta_data_create ();
859 mmeta = GNUNET_CONTAINER_meta_data_duplicate (meta);
860 uris = GNUNET_FS_uri_to_string (uri);
861 slen = strlen (uris) + 1;
862 idlen = strlen (identifier);
864 nidlen = strlen (update) + 1;
867 mdsize = GNUNET_CONTAINER_meta_data_get_serialized_size (mmeta);
868 size = sizeof (struct SBlock) + slen + nidlen + mdsize;
869 if (size > MAX_SBLOCK_SIZE)
871 size = MAX_SBLOCK_SIZE;
872 mdsize = size - (sizeof (struct SBlock) + slen + nidlen);
874 sb = GNUNET_malloc (sizeof (struct SBlock) + size);
875 dest = (char *) &sb[1];
877 memcpy (dest, update, nidlen);
881 memcpy (dest, uris, slen);
884 mdsize = GNUNET_CONTAINER_meta_data_serialize (mmeta,
887 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
888 GNUNET_CONTAINER_meta_data_destroy (mmeta);
895 _("Internal error."));
898 size = sizeof (struct SBlock) + mdsize + slen + nidlen;
899 sb_enc = GNUNET_malloc (size);
900 GNUNET_CRYPTO_hash (identifier, idlen, &key);
901 GNUNET_CRYPTO_hash (&key, sizeof (GNUNET_HashCode), &id);
902 sks_uri = GNUNET_malloc (sizeof (struct GNUNET_FS_Uri));
904 GNUNET_CRYPTO_rsa_key_get_public (namespace->key, &sb_enc->subspace);
905 GNUNET_CRYPTO_hash (&sb_enc->subspace,
906 sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded),
907 &sks_uri->data.sks.namespace);
908 sks_uri->data.sks.identifier = GNUNET_strdup (identifier);
909 GNUNET_CRYPTO_hash_xor (&id,
910 &sks_uri->data.sks.namespace,
911 &sb_enc->identifier);
912 GNUNET_CRYPTO_hash_to_aes_key (&key, &sk, &iv);
913 GNUNET_CRYPTO_aes_encrypt (&sb[1],
914 size - sizeof (struct SBlock),
918 sb_enc->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_FS_SBLOCK);
919 sb_enc->purpose.size = htonl(slen + mdsize + nidlen
920 + sizeof(struct SBlock)
921 - sizeof(struct GNUNET_CRYPTO_RsaSignature));
922 GNUNET_assert (GNUNET_OK ==
923 GNUNET_CRYPTO_rsa_sign (namespace->key,
925 &sb_enc->signature));
926 psc = GNUNET_malloc (sizeof(struct PublishSksContext));
929 psc->namespace = namespace;
931 psc->cont_cls = cont_cls;
932 if (0 != (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
934 GNUNET_free (sb_enc);
941 psc->dsh = GNUNET_DATASTORE_connect (h->cfg);
942 if (NULL == psc->dsh)
944 GNUNET_free (sb_enc);
948 _("Failed to connect to datastore."));
951 GNUNET_CRYPTO_hash_xor (&sks_uri->data.sks.namespace,
956 psc->nsn = GNUNET_malloc (sizeof (struct NamespaceUpdateNode));
957 psc->nsn->id = GNUNET_strdup (identifier);
958 psc->nsn->update = GNUNET_strdup (update);
959 psc->nsn->md = GNUNET_CONTAINER_meta_data_duplicate (meta);
960 psc->nsn->uri = GNUNET_FS_uri_dup (uri);
962 GNUNET_DATASTORE_put (psc->dsh,
967 GNUNET_BLOCK_TYPE_FS_SBLOCK,
968 bo->content_priority,
970 bo->replication_level,
973 GNUNET_CONSTANTS_SERVICE_TIMEOUT,
977 GNUNET_free (sb_enc);
982 * Closure for 'process_update_node'.
984 struct ProcessUpdateClosure
987 * Function to call for each node.
989 GNUNET_FS_IdentifierProcessor ip;
999 * Call the iterator in the closure for each node.
1001 * @param cls closure (of type 'struct ProcessUpdateClosure *')
1002 * @param key current key code
1003 * @param value value in the hash map (of type 'struct NamespaceUpdateNode *')
1004 * @return GNUNET_YES if we should continue to
1009 process_update_node (void *cls,
1010 const GNUNET_HashCode * key,
1013 struct ProcessUpdateClosure *pc = cls;
1014 struct NamespaceUpdateNode *nsn = value;
1026 * Closure for 'find_trees'.
1028 struct FindTreeClosure
1031 * Namespace we are operating on.
1033 struct GNUNET_FS_Namespace *namespace;
1036 * Array with 'head's of TREEs.
1038 struct NamespaceUpdateNode **tree_array;
1041 * Size of 'tree_array'
1043 unsigned int tree_array_size;
1046 * Current generational ID used.
1051 * Identifier for the current TREE, or UINT_MAX for none yet.
1058 * Find all nodes reachable from the current node (including the
1059 * current node itself). If they are in no tree, add them to the
1060 * current one. If they are the head of another tree, merge the
1061 * trees. If they are in the middle of another tree, let them be.
1062 * We can tell that a node is already in an tree by checking if
1063 * its 'nug' field is set to the current 'nug' value. It is the
1064 * head of an tree if it is in the 'tree_array' under its respective
1067 * In short, we're trying to find the smallest number of tree to
1068 * cover a directed graph.
1070 * @param cls closure (of type 'struct FindTreeClosure')
1071 * @param key current key code
1072 * @param value value in the hash map
1073 * @return GNUNET_YES if we should continue to
1078 find_trees (void *cls,
1079 const GNUNET_HashCode * key,
1082 struct FindTreeClosure *fc = cls;
1083 struct NamespaceUpdateNode *nsn = value;
1086 if (nsn->nug == fc->nug)
1088 if (nsn->tree_id == UINT_MAX)
1089 return GNUNET_YES; /* circular */
1090 GNUNET_assert (nsn->tree_id < fc->tree_array_size);
1091 if (fc->tree_array[nsn->tree_id] != nsn)
1092 return GNUNET_YES; /* part of "another" (directed) TREE,
1093 and not root of it, end trace */
1094 if (nsn->tree_id == fc->id)
1095 return GNUNET_YES; /* that's our own root (can this be?) */
1096 /* merge existing TREE, we have a root for both */
1097 fc->tree_array[nsn->tree_id] = NULL;
1098 if (fc->id == UINT_MAX)
1099 fc->id = nsn->tree_id; /* take over ID */
1104 nsn->tree_id = UINT_MAX; /* mark as undef */
1106 GNUNET_CRYPTO_hash (nsn->update,
1107 strlen (nsn->update),
1109 GNUNET_CONTAINER_multihashmap_get_multiple (fc->namespace->update_map,
1119 * List all of the identifiers in the namespace for which we could
1120 * produce an update. Namespace updates form a graph where each node
1121 * has a name. Each node can have any number of URI/meta-data entries
1122 * which can each be linked to other nodes. Cycles are possible.
1124 * Calling this function with "next_id" NULL will cause the library to
1125 * call "ip" with a root for each strongly connected component of the
1126 * graph (a root being a node from which all other nodes in the Tree
1129 * Calling this function with "next_id" being the name of a node will
1130 * cause the library to call "ip" with all children of the node. Note
1131 * that cycles within the final tree are possible (including self-loops).
1132 * I know, odd definition of a tree, but the GUI will display an actual
1133 * tree (GtkTreeView), so that's what counts for the term here.
1135 * @param namespace namespace to inspect for updateable content
1136 * @param next_id ID to look for; use NULL to look for tree roots
1137 * @param ip function to call on each updateable identifier
1138 * @param ip_cls closure for ip
1141 GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Namespace *namespace,
1142 const char *next_id,
1143 GNUNET_FS_IdentifierProcessor ip,
1149 struct NamespaceUpdateNode *nsn;
1150 struct ProcessUpdateClosure pc;
1151 struct FindTreeClosure fc;
1153 if (namespace->update_nodes == NULL)
1154 read_update_information_graph (namespace);
1155 if (namespace->update_nodes == NULL)
1158 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1159 "No updateable nodes found for ID `%s'\n",
1162 return; /* no nodes */
1164 if (namespace->update_map == NULL)
1166 /* need to construct */
1167 namespace->update_map = GNUNET_CONTAINER_multihashmap_create (2 + 3 * namespace->update_node_count / 4);
1168 for (i=0;i<namespace->update_node_count;i++)
1170 nsn = namespace->update_nodes[i];
1171 GNUNET_CRYPTO_hash (nsn->id,
1174 GNUNET_CONTAINER_multihashmap_put (namespace->update_map,
1177 GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
1180 if (next_id != NULL)
1182 GNUNET_CRYPTO_hash (next_id,
1187 GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map,
1189 &process_update_node,
1194 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1195 "Calculating TREEs to find roots of update trees\n");
1197 /* Find heads of TREEs in update graph */
1198 nug = ++namespace->nug_gen;
1199 fc.tree_array = NULL;
1200 fc.tree_array_size = 0;
1202 for (i=0;i<namespace->update_node_count;i++)
1204 nsn = namespace->update_nodes[i];
1205 if (nsn->nug == nug)
1208 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1209 "TREE of node `%s' is %u\n",
1213 continue; /* already placed in TREE */
1215 GNUNET_CRYPTO_hash (nsn->update,
1216 strlen (nsn->update),
1221 fc.namespace = namespace;
1222 GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map,
1226 if (fc.id == UINT_MAX)
1228 /* start new TREE */
1229 for (fc.id=0;fc.id<fc.tree_array_size;fc.id++)
1231 if (fc.tree_array[fc.id] == NULL)
1233 fc.tree_array[fc.id] = nsn;
1234 nsn->tree_id = fc.id;
1238 if (fc.id == fc.tree_array_size)
1240 GNUNET_array_append (fc.tree_array,
1243 nsn->tree_id = fc.id;
1246 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1247 "Starting new TREE %u with node `%s'\n",
1251 /* put all nodes with same identifier into this TREE */
1252 GNUNET_CRYPTO_hash (nsn->id,
1255 fc.id = nsn->tree_id;
1257 fc.namespace = namespace;
1258 GNUNET_CONTAINER_multihashmap_get_multiple (namespace->update_map,
1265 /* make head of TREE "id" */
1266 fc.tree_array[fc.id] = nsn;
1267 nsn->tree_id = fc.id;
1270 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1271 "TREE of node `%s' is %u\n",
1276 for (i=0;i<fc.tree_array_size;i++)
1278 nsn = fc.tree_array[i];
1282 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1283 "Root of TREE %u is node `%s'\n",
1295 GNUNET_array_grow (fc.tree_array,
1299 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1300 "Done processing TREEs\n");
1305 /* end of fs_namespace.c */