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