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