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  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_constants.h"
  28 #include "gnunet_signatures.h"
  29 #include "gnunet_util_lib.h"
  30 #include "gnunet_fs_service.h"
  31 #include "fs_api.h"
  32 #include "fs_publish_ublock.h"
  33
  34
  35 /**
  36  * Information about an (updateable) node in the
  37  * namespace.
  38  */
  39 struct NamespaceUpdateNode
  40 {
  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 /**
  76  * Handle to update information for a namespace.
  77  */
  78 struct GNUNET_FS_UpdateInformationGraph
  79 {
  80
  81   /**
  82    * Handle to the FS service context.
  83    */
  84   struct GNUNET_FS_Handle *h;
  85
  86   /**
  87    * Array with information about nodes in the namespace.
  88    */
  89   struct NamespaceUpdateNode **update_nodes;
  90
  91   /**
  92    * Private key for the namespace.
  93    */
  94   struct GNUNET_CRYPTO_EccPrivateKey ns;
  95
  96   /**
  97    * Hash map mapping identifiers of update nodes
  98    * to the update nodes (initialized on-demand).
  99    */
 100   struct GNUNET_CONTAINER_MultiHashMap *update_map;
 101
 102   /**
 103    * Size of the update nodes array.
 104    */
 105   unsigned int update_node_count;
 106
 107   /**
 108    * Reference counter.
 109    */
 110   unsigned int rc;
 111
 112   /**
 113    * Generator for unique nug numbers.
 114    */
 115   unsigned int nug_gen;
 116 };
 117
 118
 119 /**
 120  * Return the name of the directory in which we store
 121  * the update information graph for the given local namespace.
 122  *
 123  * @param ns namespace handle
 124  * @return NULL on error, otherwise the name of the directory
 125  */
 126 static char *
 127 get_update_information_directory (struct GNUNET_FS_Handle *h,
 128                                   const struct GNUNET_CRYPTO_EccPrivateKey *ns)
 129 {
 130   char *dn;
 131   char *ret;
 132   struct GNUNET_CRYPTO_EccPublicKey pub;
 133   struct GNUNET_CRYPTO_ShortHashCode hc;
 134   struct GNUNET_CRYPTO_ShortHashAsciiEncoded enc;
 135
 136   if (GNUNET_OK !=
 137       GNUNET_CONFIGURATION_get_value_filename (h->cfg, "FS", "UPDATE_DIR",
 138                                                &dn))
 139   {
 140     GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
 141                                "fs", "UPDATE_DIR");
 142     return NULL;
 143   }
 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,
 147                                    &enc);
 148   GNUNET_asprintf (&ret, "%s%s%s",
 149                    dn,
 150                    DIR_SEPARATOR_STR,
 151                    (const char *) enc.short_encoding);
 152   GNUNET_free (dn);
 153   return ret;
 154 }
 155
 156
 157 /**
 158  * Release memory occupied by UIG datastructure.
 159  *
 160  * @param uig data structure to free
 161  */
 162 static void
 163 free_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
 164 {
 165   unsigned int i;
 166   struct NamespaceUpdateNode *nsn;
 167
 168   for (i = 0; i < uig->update_node_count; i++)
 169   {
 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);
 175     GNUNET_free (nsn);
 176   }
 177   GNUNET_array_grow (uig->update_nodes, uig->update_node_count,
 178                      0);
 179   if (NULL != uig->update_map)
 180     GNUNET_CONTAINER_multihashmap_destroy (uig->update_map);
 181   GNUNET_free (uig);
 182 }
 183
 184
 185 /**
 186  * Write the namespace update node graph to a file.
 187  *
 188  * @param ns namespace to dump
 189  */
 190 static void
 191 write_update_information_graph (struct GNUNET_FS_UpdateInformationGraph *uig)
 192 {
 193   char *fn;
 194   struct GNUNET_BIO_WriteHandle *wh;
 195   unsigned int i;
 196   struct NamespaceUpdateNode *n;
 197   char *uris;
 198
 199   fn = get_update_information_directory (uig->h,
 200                                          &uig->ns);
 201   wh = GNUNET_BIO_write_open (fn);
 202   if (NULL == wh)
 203   {
 204     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
 205                 _("Failed to open `%s' for writing: %s\n"), STRERROR (errno));
 206     GNUNET_free (fn);
 207     return;
 208   }
 209   if (GNUNET_OK != GNUNET_BIO_write_int32 (wh, uig->update_node_count))
 210     goto END;
 211   for (i = 0; i < uig->update_node_count; i++)
 212   {
 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)))
 219     {
 220       GNUNET_free (uris);
 221       break;
 222     }
 223     GNUNET_free (uris);
 224   }
 225 END:
 226   if (GNUNET_OK != GNUNET_BIO_write_close (wh))
 227     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to write `%s': %s\n"),
 228                 STRERROR (errno));
 229   GNUNET_free (fn);
 230 }
 231
 232
 233 /**
 234  * Read the namespace update node graph from a file.
 235  *
 236  * @param h FS handle to use
 237  * @param ns namespace to read
 238  * @return update graph, never NULL
 239  */
 240 static struct GNUNET_FS_UpdateInformationGraph *
 241 read_update_information_graph (struct GNUNET_FS_Handle *h,
 242                                const struct GNUNET_CRYPTO_EccPrivateKey *ns)
 243 {
 244   struct GNUNET_FS_UpdateInformationGraph *uig;
 245   char *fn;
 246   struct GNUNET_BIO_ReadHandle *rh;
 247   unsigned int i;
 248   struct NamespaceUpdateNode *n;
 249   char *uris;
 250   uint32_t count;
 251   char *emsg;
 252
 253   uig = GNUNET_new (struct GNUNET_FS_UpdateInformationGraph);
 254   uig->h = h;
 255   uig->ns = *ns;
 256   fn = get_update_information_directory (h, ns);
 257   if (GNUNET_YES != GNUNET_DISK_file_test (fn))
 258   {
 259     GNUNET_free (fn);
 260     return uig;
 261   }
 262   rh = GNUNET_BIO_read_open (fn);
 263   if (NULL == rh)
 264   {
 265     GNUNET_free (fn);
 266     return uig;
 267   }
 268   if (GNUNET_OK != GNUNET_BIO_read_int32 (rh, &count))
 269   {
 270     GNUNET_break (0);
 271     goto ERROR;
 272   }
 273   if (count > 1024 * 1024)
 274   {
 275     GNUNET_break (0);
 276     goto ERROR;
 277   }
 278   if (0 == count)
 279   {
 280     GNUNET_break (GNUNET_OK == GNUNET_BIO_read_close (rh, NULL));
 281     GNUNET_free (fn);
 282     return uig;
 283   }
 284   uig->update_nodes =
 285     GNUNET_malloc (count * sizeof (struct NamespaceUpdateNode *));
 286
 287   for (i = 0; i < count; i++)
 288   {
 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)) ||
 292         (GNUNET_OK !=
 293          GNUNET_BIO_read_string (rh, "update-id", &n->update, 1024)) ||
 294         (GNUNET_OK != GNUNET_BIO_read_string (rh, "uri", &uris, 1024 * 2)))
 295     {
 296       GNUNET_break (0);
 297       GNUNET_free_non_null (n->id);
 298       GNUNET_free_non_null (n->update);
 299       if (n->md != NULL)
 300         GNUNET_CONTAINER_meta_data_destroy (n->md);
 301       GNUNET_free (n);
 302       break;
 303     }
 304     n->uri = GNUNET_FS_uri_parse (uris, &emsg);
 305     GNUNET_free (uris);
 306     if (n->uri == NULL)
 307     {
 308       GNUNET_break (0);
 309       GNUNET_free (emsg);
 310       GNUNET_free (n->id);
 311       GNUNET_free_non_null (n->update);
 312       GNUNET_CONTAINER_meta_data_destroy (n->md);
 313       GNUNET_free (n);
 314       break;
 315     }
 316     uig->update_nodes[i] = n;
 317   }
 318   uig->update_node_count = i;
 319   if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
 320   {
 321     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to read `%s': %s\n"),
 322                 fn, emsg);
 323     GNUNET_free (emsg);
 324   }
 325   return uig;
 326 ERROR:
 327   if (GNUNET_OK != GNUNET_BIO_read_close (rh, &emsg))
 328   {
 329     GNUNET_log (GNUNET_ERROR_TYPE_ERROR, _("Failed to read `%s': %s\n"),
 330                 fn, emsg);
 331     GNUNET_free (emsg);
 332   }
 333   GNUNET_free (fn);
 334   return uig;
 335 }
 336
 337
 338 /**
 339  * Context for the SKS publication.
 340  */
 341 struct GNUNET_FS_PublishSksContext
 342 {
 343
 344   /**
 345    * URI of the new entry in the namespace.
 346    */
 347   struct GNUNET_FS_Uri *uri;
 348
 349   /**
 350    * Namespace update node to add to namespace on success (or to be
 351    * deleted if publishing failed).
 352    */
 353   struct NamespaceUpdateNode *nsn;
 354
 355   /**
 356    * Namespace we're publishing to.
 357    */
 358   struct GNUNET_CRYPTO_EccPrivateKey ns;
 359
 360   /**
 361    * Handle to the datastore.
 362    */
 363   struct GNUNET_DATASTORE_Handle *dsh;
 364
 365   /**
 366    * Handle to FS.
 367    */
 368   struct GNUNET_FS_Handle *h;
 369
 370   /**
 371    * Function to call once we're done.
 372    */
 373   GNUNET_FS_PublishContinuation cont;
 374
 375   /**
 376    * Closure for cont.
 377    */
 378   void *cont_cls;
 379
 380   /**
 381    * Handle for our UBlock operation request.
 382    */
 383   struct GNUNET_FS_PublishUblockContext *uc;
 384 };
 385
 386
 387 /**
 388  * Function called by the UBlock construction with
 389  * the result from the PUT (UBlock) request.
 390  *
 391  * @param cls closure of type "struct GNUNET_FS_PublishSksContext*"
 392  * @param msg error message (or NULL)
 393  */
 394 static void
 395 sks_publish_cont (void *cls,
 396                   const char *msg)
 397 {
 398   struct GNUNET_FS_PublishSksContext *psc = cls;
 399   struct GNUNET_FS_UpdateInformationGraph *uig;
 400
 401   psc->uc = NULL;
 402   if (NULL != msg)
 403   {
 404     if (NULL != psc->cont)
 405       psc->cont (psc->cont_cls, NULL, msg);
 406     GNUNET_FS_publish_sks_cancel (psc);
 407     return;
 408   }
 409   if (NULL != psc->nsn)
 410   {
 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,
 415                                          &psc->ns);
 416     GNUNET_array_append (uig->update_nodes,
 417                          uig->update_node_count,
 418                          psc->nsn);
 419     psc->nsn = NULL;
 420     write_update_information_graph (uig);
 421     free_update_information_graph (uig);
 422   }
 423   if (NULL != psc->cont)
 424     psc->cont (psc->cont_cls, psc->uri, NULL);
 425   GNUNET_FS_publish_sks_cancel (psc);
 426 }
 427
 428
 429 /**
 430  * Publish an SBlock on GNUnet.
 431  *
 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)
 443  */
 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)
 453 {
 454   struct GNUNET_FS_PublishSksContext *psc;
 455   struct GNUNET_FS_Uri *sks_uri;
 456
 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);
 462
 463   psc = GNUNET_new (struct GNUNET_FS_PublishSksContext);
 464   psc->h = h;
 465   psc->uri = sks_uri;
 466   psc->cont = cont;
 467   psc->cont_cls = cont_cls;
 468   psc->ns = *ns;
 469   if (0 == (options & GNUNET_FS_PUBLISH_OPTION_SIMULATE_ONLY))
 470   {
 471     psc->dsh = GNUNET_DATASTORE_connect (h->cfg);
 472     if (NULL == psc->dsh)
 473     {
 474       sks_publish_cont (psc,
 475                         _("Failed to connect to datastore."));
 476       return NULL;
 477     }
 478   }
 479   if (NULL != update)
 480   {
 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);
 486   }
 487   psc->uc = GNUNET_FS_publish_ublock_ (h,
 488                                        psc->dsh,
 489                                        identifier,
 490                                        update,
 491                                        ns,
 492                                        meta,
 493                                        uri,
 494                                        bo,
 495                                        options,
 496                                        &sks_publish_cont,
 497                                        psc);
 498   return psc;
 499 }
 500
 501
 502 /**
 503  * Abort the SKS publishing operation.
 504  *
 505  * @param psc context of the operation to abort.
 506  */
 507 void
 508 GNUNET_FS_publish_sks_cancel (struct GNUNET_FS_PublishSksContext *psc)
 509 {
 510   if (NULL != psc->uc)
 511   {
 512     GNUNET_FS_publish_ublock_cancel_ (psc->uc);
 513     psc->uc = NULL;
 514   }
 515   if (NULL != psc->dsh)
 516   {
 517     GNUNET_DATASTORE_disconnect (psc->dsh, GNUNET_NO);
 518     psc->dsh = NULL;
 519   }
 520   GNUNET_FS_uri_destroy (psc->uri);
 521   if (NULL != psc->nsn)
 522   {
 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);
 528   }
 529   GNUNET_free (psc);
 530 }
 531
 532
 533 /**
 534  * Closure for 'process_update_node'.
 535  */
 536 struct ProcessUpdateClosure
 537 {
 538   /**
 539    * Function to call for each node.
 540    */
 541   GNUNET_FS_IdentifierProcessor ip;
 542
 543   /**
 544    * Closure for 'ip'.
 545    */
 546   void *ip_cls;
 547 };
 548
 549
 550 /**
 551  * Call the iterator in the closure for each node.
 552  *
 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
 557  *         iterate,
 558  *         GNUNET_NO if not.
 559  */
 560 static int
 561 process_update_node (void *cls,
 562                      const struct GNUNET_HashCode *key,
 563                      void *value)
 564 {
 565   struct ProcessUpdateClosure *pc = cls;
 566   struct NamespaceUpdateNode *nsn = value;
 567
 568   pc->ip (pc->ip_cls,
 569           nsn->id,
 570           nsn->uri,
 571           nsn->md,
 572           nsn->update);
 573   return GNUNET_YES;
 574 }
 575
 576
 577 /**
 578  * Closure for 'find_trees'.
 579  */
 580 struct FindTreeClosure
 581 {
 582   /**
 583    * UIG we are operating on.
 584    */
 585   struct GNUNET_FS_UpdateInformationGraph *uig;
 586
 587   /**
 588    * Array with 'head's of TREEs.
 589    */
 590   struct NamespaceUpdateNode **tree_array;
 591
 592   /**
 593    * Size of 'tree_array'
 594    */
 595   unsigned int tree_array_size;
 596
 597   /**
 598    * Current generational ID used.
 599    */
 600   unsigned int nug;
 601
 602   /**
 603    * Identifier for the current TREE, or UINT_MAX for none yet.
 604    */
 605   unsigned int id;
 606 };
 607
 608
 609 /**
 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
 617  * 'tree_id'.
 618  *
 619  * In short, we're trying to find the smallest number of tree to
 620  * cover a directed graph.
 621  *
 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
 626  *         iterate,
 627  *         GNUNET_NO if not.
 628  */
 629 static int
 630 find_trees (void *cls,
 631             const struct GNUNET_HashCode *key,
 632             void *value)
 633 {
 634   struct FindTreeClosure *fc = cls;
 635   struct NamespaceUpdateNode *nsn = value;
 636   struct GNUNET_HashCode hc;
 637
 638   if (nsn->nug == fc->nug)
 639   {
 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 */
 652   }
 653   else
 654   {
 655     nsn->nug = fc->nug;
 656     nsn->tree_id = UINT_MAX;    /* mark as undef */
 657     /* trace */
 658     GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
 659     GNUNET_CONTAINER_multihashmap_get_multiple (fc->uig->update_map, &hc,
 660                                                 &find_trees, fc);
 661   }
 662   return GNUNET_YES;
 663 }
 664
 665
 666 /**
 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.
 671  *
 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
 675  * are reachable).
 676  *
 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.
 682  *
 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
 688  */
 689 void
 690 GNUNET_FS_namespace_list_updateable (struct GNUNET_FS_Handle *h,
 691                                      const struct GNUNET_CRYPTO_EccPrivateKey *ns,
 692                                      const char *next_id,
 693                                      GNUNET_FS_IdentifierProcessor ip,
 694                                      void *ip_cls)
 695 {
 696   unsigned int i;
 697   unsigned int nug;
 698   struct GNUNET_HashCode hc;
 699   struct NamespaceUpdateNode *nsn;
 700   struct ProcessUpdateClosure pc;
 701   struct FindTreeClosure fc;
 702   struct GNUNET_FS_UpdateInformationGraph *uig;
 703
 704   uig = read_update_information_graph (h, ns);
 705   if (NULL == uig->update_nodes)
 706   {
 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 */
 711   }
 712   uig->update_map =
 713     GNUNET_CONTAINER_multihashmap_create (2 +
 714                                           3 * uig->update_node_count /
 715                                           4,
 716                                           GNUNET_NO);
 717   for (i = 0; i < uig->update_node_count; i++)
 718   {
 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);
 723   }
 724   if (NULL != next_id)
 725   {
 726     GNUNET_CRYPTO_hash (next_id, strlen (next_id), &hc);
 727     pc.ip = ip;
 728     pc.ip_cls = ip_cls;
 729     GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
 730                                                 &process_update_node, &pc);
 731     free_update_information_graph (uig);
 732     return;
 733   }
 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;
 740
 741   for (i = 0; i < uig->update_node_count; i++)
 742   {
 743     nsn = uig->update_nodes[i];
 744     if (nsn->nug == nug)
 745     {
 746       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "TREE of node `%s' is %u\n", nsn->id,
 747                   nsn->nug);
 748       continue;                 /* already placed in TREE */
 749     }
 750     GNUNET_CRYPTO_hash (nsn->update, strlen (nsn->update), &hc);
 751     nsn->nug = nug;
 752     nsn->tree_id = UINT_MAX;
 753     fc.id = UINT_MAX;
 754     fc.nug = nug;
 755     fc.uig = uig;
 756     GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
 757                                                 &find_trees, &fc);
 758     if (UINT_MAX == fc.id)
 759     {
 760       /* start new TREE */
 761       for (fc.id = 0; fc.id < fc.tree_array_size; fc.id++)
 762       {
 763         if (NULL == fc.tree_array[fc.id])
 764         {
 765           fc.tree_array[fc.id] = nsn;
 766           nsn->tree_id = fc.id;
 767           break;
 768         }
 769       }
 770       if (fc.id == fc.tree_array_size)
 771       {
 772         GNUNET_array_append (fc.tree_array, fc.tree_array_size, nsn);
 773         nsn->tree_id = fc.id;
 774       }
 775       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 776                   "Starting new TREE %u with node `%s'\n", nsn->tree_id,
 777                   nsn->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;
 781       fc.nug = nug;
 782       fc.uig = uig;
 783       GNUNET_CONTAINER_multihashmap_get_multiple (uig->update_map, &hc,
 784                                                   &find_trees, &fc);
 785     }
 786     else
 787     {
 788       /* make head of TREE "id" */
 789       fc.tree_array[fc.id] = nsn;
 790       nsn->tree_id = fc.id;
 791     }
 792     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 793                 "TREE of node `%s' is %u\n", nsn->id,
 794                 fc.id);
 795   }
 796   for (i = 0; i < fc.tree_array_size; i++)
 797   {
 798     nsn = fc.tree_array[i];
 799     if (NULL != nsn)
 800     {
 801       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Root of TREE %u is node `%s'\n", i,
 802                   nsn->id);
 803       ip (ip_cls, nsn->id, nsn->uri, nsn->md, nsn->update);
 804     }
 805   }
 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);
 809 }
 810
 811
 812 /* end of fs_namespace.c */