src/fs/fs_directory.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2003, 2004, 2006, 2009 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 2, 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_directory.c
  23  * @brief Helper functions for building directories.
  24  * @author Christian Grothoff
  25  *
  26  * TODO:
  27  * - modify directory builder API to support incremental
  28  *   generation of directories (to allow directories that
  29  *   would not fit into memory to be created)
  30  * - modify directory processor API to support incremental
  31  *   iteration over FULL directories (without missing entries)
  32  *   to allow access to directories that do not fit entirely
  33  *   into memory
  34  */
  35 #include "platform.h"
  36 #include "gnunet_fs_service.h"
  37 #include "fs.h"
  38
  39 /**
  40  * String that is used to indicate that a file
  41  * is a GNUnet directory.
  42  */
  43 #define GNUNET_DIRECTORY_MAGIC "\211GND\r\n\032\n"
  44
  45
  46 /**
  47  * Does the meta-data claim that this is a directory?
  48  * Checks if the mime-type is that of a GNUnet directory.
  49  *
  50  * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if
  51  *  we have no mime-type information (treat as 'GNUNET_NO')
  52  */
  53 int
  54 GNUNET_FS_meta_data_test_for_directory (const struct GNUNET_CONTAINER_MetaData *md)
  55 {
  56   char *mime;
  57   int ret;
  58
  59   if (NULL == md)
  60     return GNUNET_SYSERR;
  61   mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_METATYPE_MIMETYPE);
  62   if (mime == NULL)
  63     return GNUNET_SYSERR;
  64   ret = (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME)) ? GNUNET_YES : GNUNET_NO;
  65   GNUNET_free (mime);
  66   return ret;
  67 }
  68
  69
  70 /**
  71  * Set the MIMETYPE information for the given
  72  * metadata to "application/gnunet-directory".
  73  *
  74  * @param md metadata to add mimetype to
  75  */
  76 void
  77 GNUNET_FS_meta_data_make_directory (struct GNUNET_CONTAINER_MetaData *md)
  78 {
  79   char *mime;
  80
  81   mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_METATYPE_MIMETYPE);
  82   if (mime != NULL)
  83     {
  84       GNUNET_break (0 == strcmp (mime,
  85                                  GNUNET_FS_DIRECTORY_MIME));
  86       GNUNET_free (mime);
  87       return;
  88     }
  89   GNUNET_CONTAINER_meta_data_insert (md,
  90                                      "<gnunet>",
  91                                      EXTRACTOR_METATYPE_MIMETYPE,
  92                                      EXTRACTOR_METAFORMAT_UTF8,
  93                                      "text/plain",
  94                                      GNUNET_FS_DIRECTORY_MIME,
  95                                      strlen (GNUNET_FS_DIRECTORY_MIME)+1);
  96 }
  97
  98
  99 /**
 100  * Closure for 'find_full_data'.
 101  */
 102 struct GetFullDataClosure
 103 {
 104
 105   /**
 106    * Extracted binary meta data.
 107    */
 108   void *data;
 109
 110   /**
 111    * Number of bytes stored in data.
 112    */
 113   size_t size;
 114 };
 115
 116
 117 /**
 118  * Type of a function that libextractor calls for each
 119  * meta data item found.
 120  *
 121  * @param cls closure (user-defined)
 122  * @param plugin_name name of the plugin that produced this value;
 123  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 124  *        used in the main libextractor library and yielding
 125  *        meta data).
 126  * @param type libextractor-type describing the meta data
 127  * @param format basic format information about data
 128  * @param data_mime_type mime-type of data (not of the original file);
 129  *        can be NULL (if mime-type is not known)
 130  * @param data actual meta-data found
 131  * @param data_len number of bytes in data
 132  * @return 0 to continue extracting, 1 to abort
 133  */
 134 static int
 135 find_full_data (void *cls,
 136                 const char *plugin_name,
 137                 enum EXTRACTOR_MetaType type,
 138                 enum EXTRACTOR_MetaFormat format,
 139                 const char *data_mime_type,
 140                 const char *data,
 141                 size_t data_len)
 142 {
 143   struct GetFullDataClosure *gfdc = cls;
 144
 145   if (type == EXTRACTOR_METATYPE_GNUNET_FULL_DATA)
 146     {
 147       gfdc->size = data_len;
 148       if (data_len > 0)
 149         {
 150           gfdc->data = GNUNET_malloc (data_len);
 151           memcpy (gfdc->data,
 152                   data,
 153                   data_len);
 154         }
 155       return 1;
 156     }
 157   return 0;
 158 }
 159
 160
 161 /**
 162  * Iterate over all entries in a directory.  Note that directories
 163  * are structured such that it is possible to iterate over the
 164  * individual blocks as well as over the entire directory.  Thus
 165  * a client can call this function on the buffer in the
 166  * GNUNET_FS_ProgressCallback.  Also, directories can optionally
 167  * include the contents of (small) files embedded in the directory
 168  * itself; for those files, the processor may be given the
 169  * contents of the file directly by this function.
 170  * <p>
 171  *
 172  * Note that this function maybe called on parts of directories.  Thus
 173  * parser errors should not be reported _at all_ (with GNUNET_break).
 174  * Still, if some entries can be recovered despite these parsing
 175  * errors, the function should try to do this.
 176  *
 177  * @param size number of bytes in data
 178  * @param data pointer to the beginning of the directory
 179  * @param offset offset of data in the directory
 180  * @param dep function to call on each entry
 181  * @param dep_cls closure for dep
 182  * @return GNUNET_OK if this could be a block in a directory,
 183  *         GNUNET_NO if this could be part of a directory (but not 100% OK)
 184  *         GNUNET_SYSERR if 'data' does not represent a directory
 185  */
 186 int
 187 GNUNET_FS_directory_list_contents (size_t size,
 188                                    const void *data,
 189                                    uint64_t offset,
 190                                    GNUNET_FS_DirectoryEntryProcessor dep,
 191                                    void *dep_cls)
 192 {
 193   struct GetFullDataClosure full_data;
 194   const char *cdata = data;
 195   char *emsg;
 196   uint64_t pos;
 197   uint64_t align;
 198   uint32_t mdSize;
 199   uint64_t epos;
 200   struct GNUNET_FS_Uri *uri;
 201   struct GNUNET_CONTAINER_MetaData *md;
 202   char *filename;
 203
 204   if ( (offset == 0) &&
 205        ( (size < 8 + sizeof (uint32_t)) ||
 206          (0 != memcmp (cdata, GNUNET_FS_DIRECTORY_MAGIC, 8)) ) )
 207     {
 208       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 209                   _("MAGIC mismatch.  This is not a GNUnet directory.\n"));
 210       return GNUNET_SYSERR;
 211     }
 212   pos = offset;
 213   if (offset == 0)
 214     {
 215       memcpy (&mdSize, &cdata[8], sizeof (uint32_t));
 216       mdSize = ntohl (mdSize);
 217       if (mdSize > size - 8 - sizeof (uint32_t))
 218         {
 219           /* invalid size */
 220           GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 221                       _("MAGIC mismatch.  This is not a GNUnet directory.\n"));
 222           return GNUNET_SYSERR;
 223         }
 224       md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[8 +
 225                                                          sizeof (uint32_t)],
 226                                                    mdSize);
 227       if (md == NULL)
 228         {
 229           GNUNET_break (0);
 230           return GNUNET_SYSERR; /* malformed ! */
 231         }
 232       dep (dep_cls,
 233            NULL,
 234            NULL,
 235            md,
 236            0,
 237            NULL);
 238       GNUNET_CONTAINER_meta_data_destroy (md);
 239       pos = 8 + sizeof (uint32_t) + mdSize;
 240     }
 241   while (pos < size)
 242     {
 243       /* find end of URI */
 244       if (cdata[pos] == '\0')
 245         {
 246           /* URI is never empty, must be end of block,
 247              skip to next alignment */
 248           align =
 249             ((pos / DBLOCK_SIZE) + 1) * DBLOCK_SIZE;
 250           if (align == pos)
 251             {
 252               /* if we were already aligned, still skip a block! */
 253               align += DBLOCK_SIZE;
 254             }
 255           pos = align;
 256           if (pos >= size)
 257             {
 258               /* malformed - or partial download... */
 259               break;
 260             }
 261         }
 262       epos = pos;
 263       while ((epos < size) && (cdata[epos] != '\0'))
 264         epos++;
 265       if (epos >= size)
 266         return GNUNET_NO;   /* malformed - or partial download */
 267
 268       uri = GNUNET_FS_uri_parse (&cdata[pos], &emsg);
 269       pos = epos + 1;
 270       if (uri == NULL)
 271         {
 272           GNUNET_free (emsg);
 273           pos--;                /* go back to '\0' to force going to next alignment */
 274           continue;
 275         }
 276       if (GNUNET_FS_uri_test_ksk (uri))
 277         {
 278           GNUNET_FS_uri_destroy (uri);
 279           GNUNET_break (0);
 280           return GNUNET_NO; /* illegal in directory! */
 281         }
 282
 283       memcpy (&mdSize, &cdata[pos], sizeof (uint32_t));
 284       mdSize = ntohl (mdSize);
 285       pos += sizeof (uint32_t);
 286       if (pos + mdSize > size)
 287         {
 288           GNUNET_FS_uri_destroy (uri);
 289           return GNUNET_NO; /* malformed - or partial download */
 290         }
 291
 292       md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[pos], mdSize);
 293       if (md == NULL)
 294         {
 295           GNUNET_FS_uri_destroy (uri);
 296           GNUNET_break (0);
 297           return GNUNET_NO; /* malformed ! */
 298         }
 299       pos += mdSize;
 300       filename = GNUNET_CONTAINER_meta_data_get_by_type (md,
 301                                                          EXTRACTOR_METATYPE_FILENAME);
 302       full_data.size = 0;
 303       full_data.data = NULL;
 304       GNUNET_CONTAINER_meta_data_iterate (md,
 305                                           &find_full_data,
 306                                           &full_data);
 307       if (dep != NULL)
 308         {
 309           dep (dep_cls,
 310                filename,
 311                uri,
 312                md,
 313                full_data.size,
 314                full_data.data);
 315         }
 316       GNUNET_free_non_null (full_data.data);
 317       GNUNET_free_non_null (filename);
 318       GNUNET_CONTAINER_meta_data_destroy (md);
 319       GNUNET_FS_uri_destroy (uri);
 320     }
 321   return GNUNET_OK;
 322 }
 323
 324 /**
 325  * Entries in the directory (builder).
 326  */
 327 struct BuilderEntry
 328 {
 329   /**
 330    * This is a linked list.
 331    */
 332   struct BuilderEntry *next;
 333
 334   /**
 335    * Length of this entry.
 336    */
 337   size_t len;
 338 };
 339
 340 /**
 341  * Internal state of a directory builder.
 342  */
 343 struct GNUNET_FS_DirectoryBuilder
 344 {
 345   /**
 346    * Meta-data for the directory itself.
 347    */
 348   struct GNUNET_CONTAINER_MetaData *meta;
 349
 350   /**
 351    * Head of linked list of entries.
 352    */
 353   struct BuilderEntry *head;
 354
 355   /**
 356    * Number of entires in the directory.
 357    */
 358   unsigned int count;
 359 };
 360
 361
 362 /**
 363  * Create a directory builder.
 364  *
 365  * @param mdir metadata for the directory
 366  */
 367 struct GNUNET_FS_DirectoryBuilder *
 368 GNUNET_FS_directory_builder_create (const struct GNUNET_CONTAINER_MetaData *mdir)
 369 {
 370   struct GNUNET_FS_DirectoryBuilder *ret;
 371
 372   ret = GNUNET_malloc(sizeof(struct GNUNET_FS_DirectoryBuilder));
 373   if (mdir != NULL)
 374     ret->meta = GNUNET_CONTAINER_meta_data_duplicate (mdir);
 375   else
 376     ret->meta = GNUNET_CONTAINER_meta_data_create ();
 377   GNUNET_FS_meta_data_make_directory (ret->meta);
 378   return ret;
 379 }
 380
 381
 382 /**
 383  * Add an entry to a directory.
 384  *
 385  * @param bld directory to extend
 386  * @param uri uri of the entry (must not be a KSK)
 387  * @param md metadata of the entry
 388  * @param data raw data of the entry, can be NULL, otherwise
 389  *        data must point to exactly the number of bytes specified
 390  *        by the uri which must be of type LOC or CHK
 391  */
 392 void
 393 GNUNET_FS_directory_builder_add (struct GNUNET_FS_DirectoryBuilder *bld,
 394                                  const struct GNUNET_FS_Uri *uri,
 395                                  const struct GNUNET_CONTAINER_MetaData *md,
 396                                  const void *data)
 397 {
 398   struct GNUNET_FS_Uri *curi;
 399   struct BuilderEntry *e;
 400   uint64_t fsize;
 401   uint32_t big;
 402   ssize_t ret;
 403   size_t mds;
 404   size_t mdxs;
 405   char *uris;
 406   char *ser;
 407   char *sptr;
 408   size_t slen;
 409   struct GNUNET_CONTAINER_MetaData *meta;
 410   const struct GNUNET_CONTAINER_MetaData *meta_use;
 411
 412   GNUNET_assert (! GNUNET_FS_uri_test_ksk (uri));
 413   if (NULL != data)
 414     {
 415       GNUNET_assert (! GNUNET_FS_uri_test_sks (uri));
 416       if (GNUNET_FS_uri_test_chk (uri))
 417         {
 418           fsize = GNUNET_FS_uri_chk_get_file_size (uri);
 419         }
 420       else
 421         {
 422           curi = GNUNET_FS_uri_loc_get_uri (uri);
 423           GNUNET_assert (NULL != curi);
 424           fsize = GNUNET_FS_uri_chk_get_file_size (curi);
 425           GNUNET_FS_uri_destroy (curi);
 426         }
 427     }
 428   else
 429     {
 430       fsize = 0; /* not given */
 431     }
 432   if (fsize > MAX_INLINE_SIZE)
 433     fsize = 0; /* too large */
 434   uris = GNUNET_FS_uri_to_string (uri);
 435   slen = strlen (uris) + 1;
 436   mds =
 437     GNUNET_CONTAINER_meta_data_get_serialized_size (md);
 438   meta_use = md;
 439   meta = NULL;
 440   if (fsize > 0)
 441     {
 442       meta = GNUNET_CONTAINER_meta_data_duplicate (md);
 443       GNUNET_CONTAINER_meta_data_insert (meta,
 444                                          "<gnunet>",
 445                                          EXTRACTOR_METATYPE_GNUNET_FULL_DATA,
 446                                          EXTRACTOR_METAFORMAT_BINARY,
 447                                          NULL,
 448                                          data,
 449                                          fsize);
 450       mdxs =
 451         GNUNET_CONTAINER_meta_data_get_serialized_size (meta);
 452       if ( (slen + sizeof (uint32_t) + mdxs - 1) / DBLOCK_SIZE ==
 453            (slen + sizeof (uint32_t) + mds - 1) / DBLOCK_SIZE)
 454         {
 455           /* adding full data would not cause us to cross
 456              additional blocks, so add it! */
 457           meta_use = meta;
 458           mds = mdxs;
 459         }
 460     }
 461
 462   if (mds > GNUNET_MAX_MALLOC_CHECKED / 2)
 463     mds = GNUNET_MAX_MALLOC_CHECKED / 2;
 464   e = GNUNET_malloc (sizeof(struct BuilderEntry) +
 465                      slen + mds + sizeof (uint32_t));
 466   ser = (char*) &e[1];
 467   memcpy (ser, uris, slen);
 468   GNUNET_free (uris);
 469   sptr = &ser[slen + sizeof(uint32_t)];
 470   ret = GNUNET_CONTAINER_meta_data_serialize (meta_use,
 471                                               &sptr,
 472                                               mds,
 473                                               GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
 474   if (NULL != meta)
 475     GNUNET_CONTAINER_meta_data_destroy (meta);
 476   if (ret == -1)
 477     mds = 0;
 478   else
 479     mds = ret;
 480   big = htonl (mds);
 481   memcpy (&ser[slen], &big, sizeof (uint32_t));
 482   e->len = slen + sizeof (uint32_t) + mds;
 483   e->next = bld->head;
 484   bld->head = e;
 485   bld->count++;
 486 }
 487
 488
 489 /**
 490  * Given the start and end position of a block of
 491  * data, return the end position of that data
 492  * after alignment to the DBLOCK_SIZE.
 493  */
 494 static size_t
 495 do_align (size_t start_position,
 496           size_t end_position)
 497 {
 498   size_t align;
 499
 500   align = (end_position / DBLOCK_SIZE) * DBLOCK_SIZE;
 501   if ((start_position < align) && (end_position > align))
 502     return align + end_position - start_position;
 503   return end_position;
 504 }
 505
 506
 507 /**
 508  * Compute a permuation of the blocks to
 509  * minimize the cost of alignment.  Greedy packer.
 510  *
 511  * @param start starting position for the first block
 512  * @param count size of the two arrays
 513  * @param sizes the sizes of the individual blocks
 514  * @param perm the permutation of the blocks (updated)
 515  */
 516 static void
 517 block_align (size_t start,
 518              unsigned int count,
 519              const size_t *sizes,
 520              unsigned int *perm)
 521 {
 522   unsigned int i;
 523   unsigned int j;
 524   unsigned int tmp;
 525   unsigned int best;
 526   ssize_t badness;
 527   size_t cpos;
 528   size_t cend;
 529   ssize_t cbad;
 530   unsigned int cval;
 531
 532   cpos = start;
 533   for (i = 0; i < count; i++)
 534     {
 535       start = cpos;
 536       badness = 0x7FFFFFFF;
 537       best = -1;
 538       for (j = i; j < count; j++)
 539         {
 540           cval = perm[j];
 541           cend = cpos + sizes[cval];
 542           if (cpos % DBLOCK_SIZE == 0)
 543             {
 544               /* prefer placing the largest blocks first */
 545               cbad = -(cend % DBLOCK_SIZE);
 546             }
 547           else
 548             {
 549               if (cpos / DBLOCK_SIZE ==
 550                   cend / DBLOCK_SIZE)
 551                 {
 552                   /* Data fits into the same block! Prefer small left-overs! */
 553                   cbad =
 554                     DBLOCK_SIZE - cend % DBLOCK_SIZE;
 555                 }
 556               else
 557                 {
 558                   /* Would have to waste space to re-align, add big factor, this
 559                      case is a real loss (proportional to space wasted)! */
 560                   cbad =
 561                     DBLOCK_SIZE * (DBLOCK_SIZE -
 562                                              cpos %
 563                                              DBLOCK_SIZE);
 564                 }
 565             }
 566           if (cbad < badness)
 567             {
 568               best = j;
 569               badness = cbad;
 570             }
 571         }
 572       GNUNET_assert (best != -1);
 573       tmp = perm[i];
 574       perm[i] = perm[best];
 575       perm[best] = tmp;
 576       cpos += sizes[perm[i]];
 577       cpos = do_align (start, cpos);
 578     }
 579 }
 580
 581
 582 /**
 583  * Finish building the directory.  Frees the
 584  * builder context and returns the directory
 585  * in-memory.
 586  *
 587  * @param bld directory to finish
 588  * @param rsize set to the number of bytes needed
 589  * @param rdata set to the encoded directory
 590  * @return GNUNET_OK on success
 591  */
 592 int
 593 GNUNET_FS_directory_builder_finish (struct GNUNET_FS_DirectoryBuilder *bld,
 594                                     size_t *rsize,
 595                                     void **rdata)
 596 {
 597   char *data;
 598   char *sptr;
 599   size_t *sizes;
 600   unsigned int *perm;
 601   unsigned int i;
 602   unsigned int j;
 603   struct BuilderEntry *pos;
 604   struct BuilderEntry **bes;
 605   size_t size;
 606   size_t psize;
 607   size_t off;
 608   ssize_t ret;
 609   uint32_t big;
 610
 611   size = strlen (GNUNET_DIRECTORY_MAGIC) + sizeof (uint32_t);
 612   size += GNUNET_CONTAINER_meta_data_get_serialized_size (bld->meta);
 613   sizes = NULL;
 614   perm = NULL;
 615   bes = NULL;
 616   if (0 < bld->count)
 617     {
 618       sizes = GNUNET_malloc (bld->count * sizeof (size_t));
 619       perm = GNUNET_malloc (bld->count * sizeof (unsigned int));
 620       bes = GNUNET_malloc (bld->count * sizeof (struct BuilderEntry *));
 621       pos = bld->head;
 622       for (i = 0; i < bld->count; i++)
 623         {
 624           perm[i] = i;
 625           bes[i] = pos;
 626           sizes[i] = pos->len;
 627           pos = pos->next;
 628         }
 629       block_align (size,
 630                    bld->count,
 631                    sizes,
 632                    perm);
 633       /* compute final size with alignment */
 634       for (i = 0; i < bld->count; i++)
 635         {
 636           psize = size;
 637           size += sizes[perm[i]];
 638           size = do_align (psize, size);
 639         }
 640     }
 641   *rsize = size;
 642   data = GNUNET_malloc_large (size);
 643   if (data == NULL)
 644     {
 645       GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR,
 646                            "malloc");
 647       *rsize = 0;
 648       *rdata = NULL;
 649       GNUNET_free_non_null (sizes);
 650       GNUNET_free_non_null (perm);
 651       GNUNET_free_non_null (bes);
 652       return GNUNET_SYSERR;
 653     }
 654   *rdata = data;
 655   memcpy (data, GNUNET_DIRECTORY_MAGIC, strlen (GNUNET_DIRECTORY_MAGIC));
 656   off = strlen (GNUNET_DIRECTORY_MAGIC);
 657
 658   sptr = &data[off + sizeof (uint32_t)];
 659   ret = GNUNET_CONTAINER_meta_data_serialize (bld->meta,
 660                                               &sptr,
 661                                               size - off - sizeof (uint32_t),
 662                                               GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
 663   GNUNET_assert (ret != -1);
 664   big = htonl (ret);
 665   memcpy (&data[off], &big, sizeof (uint32_t));
 666   off += sizeof (uint32_t) + ret;
 667   for (j = 0; j < bld->count; j++)
 668     {
 669       i = perm[j];
 670       psize = off;
 671       off += sizes[i];
 672       off = do_align (psize, off);
 673       memcpy (&data[off - sizes[i]],
 674               &(bes[i])[1],
 675               sizes[i]);
 676       GNUNET_free (bes[i]);
 677     }
 678   GNUNET_free_non_null (sizes);
 679   GNUNET_free_non_null (perm);
 680   GNUNET_free_non_null (bes);
 681   GNUNET_assert (off == size);
 682   GNUNET_CONTAINER_meta_data_destroy (bld->meta);
 683   GNUNET_free (bld);
 684   return GNUNET_OK;
 685 }
 686
 687
 688 /* end of fs_directory.c */