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