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