src/fs/fs_directory.c

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