src/fs/fs_namespace.c

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