src/fs/fs_namespace.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2003-2013 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 fs/fs_namespace.c
  23  * @brief publishing to namespaces, and tracking updateable entries
  24  *        for our namespaces
  25  * @author Christian Grothoff
  26  */
  27 #include "platform.h"
  28 #include "gnunet_constants.h"
  29 #include "gnunet_signatures.h"
  30 #include "gnunet_util_lib.h"
  31 #include "gnunet_fs_service.h"
  32 #include "fs_api.h"
  33 #include "fs_publish_ublock.h"
  34
  35
  36 /**
  37  * Information about an (updateable) node in the
  38  * namespace.
  39  */
  40 struct NamespaceUpdateNode {
  41   /**
  42    * Identifier for this node.
  43    */
  44   char *id;
  45
  46   /**
  47    * Identifier of children of this node.
  48    */
  49   char *update;
  50
  51   /**
  52    * Metadata for this entry.
  53    */
  54   struct GNUNET_CONTAINER_MetaData *md;
  55
  56   /**
  57    * URI of this entry in the namespace.
  58    */
  59   struct GNUNET_FS_Uri *uri;
  60
  61   /**
  62    * Namespace update generation ID.  Used to ensure
  63    * freshness of the tree_id.
  64    */
  65   unsigned int nug;
  66
  67   /**
  68    * TREE this entry belongs to (if nug is current).
  69    */
  70   unsigned int tree_id;
  71 };
  72
  73
  74 /**
  75  * Handle to update information for a namespace.
  76  */
  77 struct GNUNET_FS_UpdateInformationGraph {
  78   /**
  79    * Handle to the FS service context.
  80    */
  81   struct GNUNET_FS_Handle *h;
  82
  83   /**
  84    * Array with information about nodes in the namespace.
  85    */
  86   struct NamespaceUpdateNode **update_nodes;
  87
  88   /**
  89    * Private key for the namespace.
  90    */
  91   struct GNUNET_CRYPTO_EcdsaPrivateKey ns;
  92
  93   /**
  94    * Hash map mapping identifiers of update nodes
  95    * to the update nodes (initialized on-demand).
  96    */
  97   struct GNUNET_CONTAINER_MultiHashMap *update_map;
  98
  99   /**
 100    * Size of the update nodes array.
 101    */
 102   unsigned int update_node_count;
 103
 104   /**
 105    * Reference counter.
 106    */
 107   unsigned int rc;
 108
 109   /**
 110    * Generator for unique nug numbers.
 111    */
 112   unsigned int nug_gen;
 113 };
 114
 115
 116 /**
 117  * Return the name of the directory in which we store
 118  * the update information graph for the given local namespace.
 119  *
 120  * @param h file-sharing handle
 121  * @param ns namespace handle
 122  * @return NULL on error, otherwise the name of the directory
 123  */
 124 static char *
 125 get_update_information_directory(
 126   struct GNUNET_FS_Handle *h,
 127   const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns)
 128 {
 129   char *dn;
 130   char *ret;
 131   struct GNUNET_CRYPTO_EcdsaPublicKey pub;
 132   struct GNUNET_HashCode hc;
 133   struct GNUNET_CRYPTO_HashAsciiEncoded enc;
 134
 135   if (GNUNET_OK !=
 136       GNUNET_CONFIGURATION_get_value_filename(h->cfg, "FS", "UPDATE_DIR", &dn))
 137     {
 138       GNUNET_log_config_missing(GNUNET_ERROR_TYPE_ERROR, "fs", "UPDATE_DIR");
 139       return NULL;
 140     }
 141   GNUNET_CRYPTO_ecdsa_key_get_public(ns, &pub);
 142   GNUNET_CRYPTO_hash(&pub, sizeof(pub), &hc);
 143   GNUNET_CRYPTO_hash_to_enc(&hc, &enc);
 144   GNUNET_asprintf(&ret,
 145                   "%s%s%s",
 146                   dn,
 147                   DIR_SEPARATOR_STR,
 148                   (const char *)enc.encoding);
 149   GNUNET_free(dn);
 150   return ret;
 151 }
 152
 153
 154 /**
 155  * Release memory occupied by UIG datastructure.
 156  *
 157  * @param uig data structure to free
 158  */
 159 static void
 160 free_update_information_graph(struct GNUNET_FS_UpdateInformationGraph *uig)
 161 {
 162   unsigned int i;
 163   struct NamespaceUpdateNode *nsn;
 164
 165   for (i = 0; i < uig->update_node_count; i++)
 166     {
 167       nsn = uig->update_nodes[i];
 168       GNUNET_CONTAINER_meta_data_destroy(nsn->md);
 169       GNUNET_FS_uri_destroy(nsn->uri);
 170       GNUNET_free(nsn->id);
 171       GNUNET_free(nsn->update);
 172       GNUNET_free(nsn);
 173     }
 174   GNUNET_array_grow(uig->update_nodes, uig->update_node_count, 0);
 175   if (NULL != uig->update_map)
 176     GNUNET_CONTAINER_multihashmap_destroy(uig->update_map);
 177   GNUNET_free(uig);
 178 }
 179
 180
 181 /**
 182  * Write a namespace's update node graph to a file.
 183  *
 184  * @param uig update information graph to dump
 185  */
 186 static void
 187 write_update_information_graph(struct GNUNET_FS_UpdateInformationGraph *uig)
 188 {
 189   char *fn;
 190   struct GNUNET_BIO_WriteHandle *wh;
 191   unsigned int i;
 192   struct NamespaceUpdateNode *n;
 193   char *uris;
 194
 195   fn = get_update_information_directory(uig->h, &uig->ns);
 196   wh = GNUNET_BIO_write_open(fn);
 197   if (NULL == wh)
 198     {
 199       GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
 200                  _("Failed to open `%s' for writing: %s\n"),
 201                  fn,
 202                  strerror(errno));
 203       GNUNET_free(fn);
 204       return;
 205     }
 206   if (GNUNET_OK != GNUNET_BIO_write_int32(wh, uig->update_node_count))
 207     goto END;
 208   for (i = 0; i < uig->update_node_count; i++)
 209     {
 210       n = uig->update_nodes[i];
 211       uris = GNUNET_FS_uri_to_string(n->uri);
 212       if ((GNUNET_OK != GNUNET_BIO_write_string(wh, n->id)) ||
 213           (GNUNET_OK != GNUNET_BIO_write_meta_data(wh, n->md)) ||
 214           (GNUNET_OK != GNUNET_BIO_write_string(wh, n->update)) ||
 215           (GNUNET_OK != GNUNET_BIO_write_string(wh, uris)))
 216         {
 217           GNUNET_free(uris);
 218           break;
 219         }
 220       GNUNET_free(uris);
 221     }
 222 END:
 223   if (GNUNET_OK != GNUNET_BIO_write_close(wh))
 224     GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
 225                _("Failed to write `%s': %s\n"),
 226                fn,
 227                strerror(errno));
 228   GNUNET_free(fn);
 229 }
 230
 231
 232 /**
 233  * Read the namespace update node graph from a file.
 234  *
 235  * @param h FS handle to use
 236  * @param ns namespace to read
 237  * @return update graph, never NULL
 238  */
 239 static struct GNUNET_FS_UpdateInformationGraph *
 240 read_update_information_graph(struct GNUNET_FS_Handle *h,
 241                               const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns)
 242 {
 243   struct GNUNET_FS_UpdateInformationGraph *uig;
 244   char *fn;
 245   struct GNUNET_BIO_ReadHandle *rh;
 246   unsigned int i;
 247   struct NamespaceUpdateNode *n;
 248   char *uris;
 249   uint32_t count;
 250   char *emsg;
 251
 252   uig = GNUNET_new(struct GNUNET_FS_UpdateInformationGraph);
 253   uig->h = h;
 254   uig->ns = *ns;
 255   fn = get_update_information_directory(h, ns);
 256   if (GNUNET_YES != GNUNET_DISK_file_test(fn))
 257     {
 258       GNUNET_free(fn);
 259       return uig;
 260     }
 261   rh = GNUNET_BIO_read_open(fn);
 262   if (NULL == rh)
 263     {
 264       GNUNET_free(fn);
 265       return uig;
 266     }
 267   if (GNUNET_OK != GNUNET_BIO_read_int32(rh, &count))
 268     {
 269       GNUNET_break(0);
 270       goto END;
 271     }
 272   if (count > 1024 * 1024)
 273     {
 274       GNUNET_break(0);
 275       goto END;
 276     }
 277   if (0 == count)
 278     goto END;
 279   uig->update_nodes =
 280     GNUNET_malloc(count * sizeof(struct NamespaceUpdateNode *));
 281
 282   for (i = 0; i < count; i++)
 283     {
 284       n = GNUNET_new(struct NamespaceUpdateNode);
 285       if ((GNUNET_OK !=
 286            GNUNET_BIO_read_string(rh, "identifier", &n->id, 1024)) ||
 287           (GNUNET_OK != GNUNET_BIO_read_meta_data(rh, "meta", &n->md)) ||
 288           (GNUNET_OK !=
 289            GNUNET_BIO_read_string(rh, "update-id", &n->update, 1024)) ||
 290           (GNUNET_OK != GNUNET_BIO_read_string(rh, "uri", &uris, 1024 * 2)))
 291         {
 292           GNUNET_break(0);
 293           GNUNET_free_non_null(n->id);
 294           GNUNET_free_non_null(n->update);
 295           if (n->md != NULL)
 296             GNUNET_CONTAINER_meta_data_destroy(n->md);
 297           GNUNET_free(n);
 298           break;
 299         }
 300       n->uri = GNUNET_FS_uri_parse(uris, &emsg);
 301       GNUNET_free(uris);
 302       if (n->uri == NULL)
 303         {
 304           GNUNET_break(0);
 305           GNUNET_free(emsg);
 306           GNUNET_free(n->id);
 307           GNUNET_free_non_null(n->update);
 308           GNUNET_CONTAINER_meta_data_destroy(n->md);
 309           GNUNET_free(n);
 310           break;
 311         }
 312       uig->update_nodes[i] = n;
 313     }
 314   uig->update_node_count = i;
 315 END:
 316   if (GNUNET_OK != GNUNET_BIO_read_close(rh, &emsg))
 317     {
 318       GNUNET_log(GNUNET_ERROR_TYPE_ERROR,
 319                  _("Failed to read `%s': %s\n"),
 320                  fn,
 321                  emsg);
 322       GNUNET_free(emsg);
 323     }
 324   GNUNET_free(fn);
 325   return uig;
 326 }
 327
 328
 329 /**
 330  * Context for the SKS publication.
 331  */
 332 struct GNUNET_FS_PublishSksContext {
 333   /**
 334    * URI of the new entry in the namespace.
 335    */
 336   struct GNUNET_FS_Uri *uri;
 337
 338   /**
 339    * Namespace update node to add to namespace on success (or to be
 340    * deleted if publishing failed).
 341    */
 342   struct NamespaceUpdateNode *nsn;
 343
 344   /**
 345    * Namespace we're publishing to.
 346    */
 347   struct GNUNET_CRYPTO_EcdsaPrivateKey ns;
 348
 349   /**
 350    * Handle to the datastore.
 351    */
 352   struct GNUNET_DATASTORE_Handle *dsh;
 353
 354   /**
 355    * Handle to FS.
 356    */
 357   struct GNUNET_FS_Handle *h;
 358
 359   /**
 360    * Function to call once we're done.
 361    */
 362   GNUNET_FS_PublishContinuation cont;
 363
 364   /**
 365    * Closure for cont.
 366    */
 367   void *cont_cls;
 368
 369   /**
 370    * Handle for our UBlock operation request.
 371    */
 372   struct GNUNET_FS_PublishUblockContext *uc;
 373 };
 374
 375
 376 /**
 377  * Function called by the UBlock construction with
 378  * the result from the PUT (UBlock) request.
 379  *
 380  * @param cls closure of type "struct GNUNET_FS_PublishSksContext*"
 381  * @param msg error message (or NULL)
 382  */
 383 static void
 384 sks_publish_cont(void *cls, const char *msg)
 385 {
 386   struct GNUNET_FS_PublishSksContext *psc = cls;
 387   struct GNUNET_FS_UpdateInformationGraph *uig;
 388
 389   psc->uc = NULL;
 390   if (NULL != msg)
 391     {
 392       if (NULL != psc->cont)
 393         psc->cont(psc->cont_cls, NULL, msg);
 394       GNUNET_FS_publish_sks_cancel(psc);
 395       return;
 396     }
 397   if (NULL != psc->nsn)
 398     {
 399       /* FIXME: this can be done much more
 400        * efficiently by simply appending to the
 401        * file and overwriting the 4-byte header */
 402       uig = read_update_information_graph(psc->h, &psc->ns);
 403       GNUNET_array_append(uig->update_nodes, uig->update_node_count, psc->nsn);
 404       psc->nsn = NULL;
 405       write_update_information_graph(uig);
 406       free_update_information_graph(uig);
 407     }
 408   if (NULL != psc->cont)
 409     psc->cont(psc->cont_cls, psc->uri, NULL);
 410   GNUNET_FS_publish_sks_cancel(psc);
 411 }
 412
 413
 414 /**
 415  * Publish an SBlock on GNUnet.
 416  *
 417  * @param h handle to the file sharing subsystem
 418  * @param ns namespace to publish in
 419  * @param identifier identifier to use
 420  * @param update update identifier to use
 421  * @param meta metadata to use
 422  * @param uri URI to refer to in the SBlock
 423  * @param bo block options
 424  * @param options publication options
 425  * @param cont continuation
 426  * @param cont_cls closure for cont
 427  * @return NULL on error ('cont' will still be called)
 428  */
 429 struct GNUNET_FS_PublishSksContext *
 430 GNUNET_FS_publish_sks(struct GNUNET_FS_Handle *h,
 431                       const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns,
 432                       const char *identifier,
 433                       const char *update,
 434                       const struct GNUNET_CONTAINER_MetaData *meta,
 435                       const struct GNUNET_FS_Uri *uri,
 436                       const struct GNUNET_FS_BlockOptions *bo,
 437                       enum GNUNET_FS_PublishOptions options,
 438                       GNUNET_FS_PublishContinuation cont,
 439                       void *cont_cls)
 440 {
 441   struct GNUNET_FS_PublishSksContext *psc;
 442   struct GNUNET_FS_Uri *sks_uri;
 443
 444   sks_uri = GNUNET_new(struct GNUNET_FS_Uri);
 445   sks_uri->type = GNUNET_FS_URI_SKS;
 446   sks_uri->data.sks.identifier = GNUNET_strdup(identifier);
 447   GNUNET_CRYPTO_ecdsa_key_get_public(ns, &sks_uri->data.sks.ns);
 448
 449   psc = GNUNET_new(struct GNUNET_FS_PublishSksContext);
 450   psc->h = h;
 451   psc->uri = sks_uri;
 452   psc->cont = cont;
 453   psc->cont_cls = cont_cls;
 454   psc->ns = *ns;
 455   if (0 == (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
 456     {
 457       psc->dsh = GNUNET_DATASTORE_connect(h->cfg);
 458       if (NULL == psc->dsh)
 459         {
 460           sks_publish_cont(psc, _("Failed to connect to datastore."));
 461           return NULL;
 462         }
 463     }
 464   if (NULL != update)
 465     {
 466       psc->nsn = GNUNET_new(struct NamespaceUpdateNode);
 467       psc->nsn->id = GNUNET_strdup(identifier);
 468       psc->nsn->update = GNUNET_strdup(update);
 469       psc->nsn->md = GNUNET_CONTAINER_meta_data_duplicate(meta);
 470       psc->nsn->uri = GNUNET_FS_uri_dup(uri);
 471     }
 472   psc->uc = GNUNET_FS_publish_ublock_(h,
 473                                       psc->dsh,
 474                                       identifier,
 475                                       update,
 476                                       ns,
 477                                       meta,
 478                                       uri,
 479                                       bo,
 480                                       options,
 481                                       &sks_publish_cont,
 482                                       psc);
 483   return psc;
 484 }
 485
 486
 487 /**
 488  * Abort the SKS publishing operation.
 489  *
 490  * @param psc context of the operation to abort.
 491  */
 492 void
 493 GNUNET_FS_publish_sks_cancel(struct GNUNET_FS_PublishSksContext *psc)
 494 {
 495   if (NULL != psc->uc)
 496     {
 497       GNUNET_FS_publish_ublock_cancel_(psc->uc);
 498       psc->uc = NULL;
 499     }
 500   if (NULL != psc->dsh)
 501     {
 502       GNUNET_DATASTORE_disconnect(psc->dsh, GNUNET_NO);
 503       psc->dsh = NULL;
 504     }
 505   GNUNET_FS_uri_destroy(psc->uri);
 506   if (NULL != psc->nsn)
 507     {
 508       GNUNET_CONTAINER_meta_data_destroy(psc->nsn->md);
 509       GNUNET_FS_uri_destroy(psc->nsn->uri);
 510       GNUNET_free(psc->nsn->id);
 511       GNUNET_free(psc->nsn->update);
 512       GNUNET_free(psc->nsn);
 513     }
 514   GNUNET_free(psc);
 515 }
 516
 517
 518 /**
 519  * Closure for 'process_update_node'.
 520  */
 521 struct ProcessUpdateClosure {
 522   /**
 523    * Function to call for each node.
 524    */
 525   GNUNET_FS_IdentifierProcessor ip;
 526
 527   /**
 528    * Closure for 'ip'.
 529    */
 530   void *ip_cls;
 531 };
 532
 533
 534 /**
 535  * Call the iterator in the closure for each node.
 536  *
 537  * @param cls closure (of type 'struct ProcessUpdateClosure *')
 538  * @param key current key code
 539  * @param value value in the hash map (of type 'struct NamespaceUpdateNode *')
 540  * @return GNUNET_YES if we should continue to
 541  *         iterate,
 542  *         GNUNET_NO if not.
 543  */
 544 static int
 545 process_update_node(void *cls, const struct GNUNET_HashCode *key, void *value)
 546 {
 547   struct ProcessUpdateClosure *pc = cls;
 548   struct NamespaceUpdateNode *nsn = value;
 549
 550   pc->ip(pc->ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
 551   return GNUNET_YES;
 552 }
 553
 554
 555 /**
 556  * Closure for 'find_trees'.
 557  */
 558 struct FindTreeClosure {
 559   /**
 560    * UIG we are operating on.
 561    */
 562   struct GNUNET_FS_UpdateInformationGraph *uig;
 563
 564   /**
 565    * Array with 'head's of TREEs.
 566    */
 567   struct NamespaceUpdateNode **tree_array;
 568
 569   /**
 570    * Size of 'tree_array'
 571    */
 572   unsigned int tree_array_size;
 573
 574   /**
 575    * Current generational ID used.
 576    */
 577   unsigned int nug;
 578
 579   /**
 580    * Identifier for the current TREE, or UINT_MAX for none yet.
 581    */
 582   unsigned int id;
 583 };
 584
 585
 586 /**
 587  * Find all nodes reachable from the current node (including the
 588  * current node itself).  If they are in no tree, add them to the
 589  * current one.   If they are the head of another tree, merge the
 590  * trees.  If they are in the middle of another tree, let them be.
 591  * We can tell that a node is already in an tree by checking if
 592  * its 'nug' field is set to the current 'nug' value.  It is the
 593  * head of an tree if it is in the 'tree_array' under its respective
 594  * 'tree_id'.
 595  *
 596  * In short, we're trying to find the smallest number of tree to
 597  * cover a directed graph.
 598  *
 599  * @param cls closure (of type 'struct FindTreeClosure')
 600  * @param key current key code
 601  * @param value value in the hash map
 602  * @return GNUNET_YES if we should continue to
 603  *         iterate,
 604  *         GNUNET_NO if not.
 605  */
 606 static int
 607 find_trees(void *cls, const struct GNUNET_HashCode *key, void *value)
 608 {
 609   struct FindTreeClosure *fc = cls;
 610   struct NamespaceUpdateNode *nsn = value;
 611   struct GNUNET_HashCode hc;
 612
 613   if (nsn->nug == fc->nug)
 614     {
 615       if (UINT_MAX == nsn->tree_id)
 616         return GNUNET_YES; /* circular */
 617       GNUNET_assert(nsn->tree_id < fc->tree_array_size);
 618       if (fc->tree_array[nsn->tree_id] != nsn)
 619         return GNUNET_YES; /* part of "another" (directed) TREE,
 620                             * and not root of it, end trace */
 621       if (nsn->tree_id == fc->id)
 622         return GNUNET_YES; /* that's our own root (can this be?) */
 623       /* merge existing TREE, we have a root for both */
 624       fc->tree_array[nsn->tree_id] = NULL;
 625       if (UINT_MAX == fc->id)
 626         fc->id = nsn->tree_id; /* take over ID */
 627     }
 628   else
 629     {
 630       nsn->nug = fc->nug;
 631       nsn->tree_id = UINT_MAX; /* mark as undef */
 632       /* trace */
 633       GNUNET_CRYPTO_hash(nsn->update, strlen(nsn->update), &hc);
 634       GNUNET_CONTAINER_multihashmap_get_multiple(fc->uig->update_map,
 635                                                  &hc,
 636                                                  &find_trees,
 637                                                  fc);
 638     }
 639   return GNUNET_YES;
 640 }
 641
 642
 643 /**
 644  * List all of the identifiers in the namespace for which we could
 645  * produce an update.  Namespace updates form a graph where each node
 646  * has a name.  Each node can have any number of URI/meta-data entries
 647  * which can each be linked to other nodes.  Cycles are possible.
 648  *
 649  * Calling this function with "next_id" NULL will cause the library to
 650  * call "ip" with a root for each strongly connected component of the
 651  * graph (a root being a node from which all other nodes in the Tree
 652  * are reachable).
 653  *
 654  * Calling this function with "next_id" being the name of a node will
 655  * cause the library to call "ip" with all children of the node.  Note
 656  * that cycles within the final tree are possible (including self-loops).
 657  * I know, odd definition of a tree, but the GUI will display an actual
 658  * tree (GtkTreeView), so that's what counts for the term here.
 659  *
 660  * @param h fs handle to use
 661  * @param ns namespace to inspect for updateable content
 662  * @param next_id ID to look for; use NULL to look for tree roots
 663  * @param ip function to call on each updateable identifier
 664  * @param ip_cls closure for ip
 665  */
 666 void
 667 GNUNET_FS_namespace_list_updateable(
 668   struct GNUNET_FS_Handle *h,
 669   const struct GNUNET_CRYPTO_EcdsaPrivateKey *ns,
 670   const char *next_id,
 671   GNUNET_FS_IdentifierProcessor ip,
 672   void *ip_cls)
 673 {
 674   unsigned int i;
 675   unsigned int nug;
 676   struct GNUNET_HashCode hc;
 677   struct NamespaceUpdateNode *nsn;
 678   struct ProcessUpdateClosure pc;
 679   struct FindTreeClosure fc;
 680   struct GNUNET_FS_UpdateInformationGraph *uig;
 681
 682   uig = read_update_information_graph(h, ns);
 683   if (NULL == uig->update_nodes)
 684     {
 685       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 686                  "No updateable nodes found for ID `%s'\n",
 687                  next_id);
 688       free_update_information_graph(uig);
 689       return; /* no nodes */
 690     }
 691   uig->update_map =
 692     GNUNET_CONTAINER_multihashmap_create(2 + 3 * uig->update_node_count / 4,
 693                                          GNUNET_NO);
 694   for (i = 0; i < uig->update_node_count; i++)
 695     {
 696       nsn = uig->update_nodes[i];
 697       GNUNET_CRYPTO_hash(nsn->id, strlen(nsn->id), &hc);
 698       GNUNET_CONTAINER_multihashmap_put(
 699         uig->update_map,
 700         &hc,
 701         nsn,
 702         GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
 703     }
 704   if (NULL != next_id)
 705     {
 706       GNUNET_CRYPTO_hash(next_id, strlen(next_id), &hc);
 707       pc.ip = ip;
 708       pc.ip_cls = ip_cls;
 709       GNUNET_CONTAINER_multihashmap_get_multiple(uig->update_map,
 710                                                  &hc,
 711                                                  &process_update_node,
 712                                                  &pc);
 713       free_update_information_graph(uig);
 714       return;
 715     }
 716   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 717              "Calculating TREEs to find roots of update trees\n");
 718   /* Find heads of TREEs in update graph */
 719   nug = ++uig->nug_gen;
 720   fc.tree_array = NULL;
 721   fc.tree_array_size = 0;
 722
 723   for (i = 0; i < uig->update_node_count; i++)
 724     {
 725       nsn = uig->update_nodes[i];
 726       if (nsn->nug == nug)
 727         {
 728           GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 729                      "TREE of node `%s' is %u\n",
 730                      nsn->id,
 731                      nsn->nug);
 732           continue; /* already placed in TREE */
 733         }
 734       GNUNET_CRYPTO_hash(nsn->update, strlen(nsn->update), &hc);
 735       nsn->nug = nug;
 736       nsn->tree_id = UINT_MAX;
 737       fc.id = UINT_MAX;
 738       fc.nug = nug;
 739       fc.uig = uig;
 740       GNUNET_CONTAINER_multihashmap_get_multiple(uig->update_map,
 741                                                  &hc,
 742                                                  &find_trees,
 743                                                  &fc);
 744       if (UINT_MAX == fc.id)
 745         {
 746           /* start new TREE */
 747           for (fc.id = 0; fc.id < fc.tree_array_size; fc.id++)
 748             {
 749               if (NULL == fc.tree_array[fc.id])
 750                 {
 751                   fc.tree_array[fc.id] = nsn;
 752                   nsn->tree_id = fc.id;
 753                   break;
 754                 }
 755             }
 756           if (fc.id == fc.tree_array_size)
 757             {
 758               GNUNET_array_append(fc.tree_array, fc.tree_array_size, nsn);
 759               nsn->tree_id = fc.id;
 760             }
 761           GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 762                      "Starting new TREE %u with node `%s'\n",
 763                      nsn->tree_id,
 764                      nsn->id);
 765           /* put all nodes with same identifier into this TREE */
 766           GNUNET_CRYPTO_hash(nsn->id, strlen(nsn->id), &hc);
 767           fc.id = nsn->tree_id;
 768           fc.nug = nug;
 769           fc.uig = uig;
 770           GNUNET_CONTAINER_multihashmap_get_multiple(uig->update_map,
 771                                                      &hc,
 772                                                      &find_trees,
 773                                                      &fc);
 774         }
 775       else
 776         {
 777           /* make head of TREE "id" */
 778           fc.tree_array[fc.id] = nsn;
 779           nsn->tree_id = fc.id;
 780         }
 781       GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 782                  "TREE of node `%s' is %u\n",
 783                  nsn->id,
 784                  fc.id);
 785     }
 786   for (i = 0; i < fc.tree_array_size; i++)
 787     {
 788       nsn = fc.tree_array[i];
 789       if (NULL != nsn)
 790         {
 791           GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 792                      "Root of TREE %u is node `%s'\n",
 793                      i,
 794                      nsn->id);
 795           ip(ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
 796         }
 797     }
 798   GNUNET_array_grow(fc.tree_array, fc.tree_array_size, 0);
 799   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG, "Done processing TREEs\n");
 800   free_update_information_graph(uig);
 801 }
 802
 803
 804 /* end of fs_namespace.c */