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      SPDX-License-Identifier: AGPL3.0-or-later
  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
  55                                         GNUNET_CONTAINER_MetaData *md)
  56 {
  57   char *mime;
  58   int ret;
  59
  60   if (NULL == md)
  61     return GNUNET_SYSERR;
  62   mime = GNUNET_CONTAINER_meta_data_get_by_type (md,
  63                                                  EXTRACTOR_METATYPE_MIMETYPE);
  64   if (NULL == mime)
  65     return GNUNET_SYSERR;
  66   ret = (0 == strcasecmp (mime, GNUNET_FS_DIRECTORY_MIME)) ? GNUNET_YES :
  67         GNUNET_NO;
  68   GNUNET_free (mime);
  69   return ret;
  70 }
  71
  72
  73 /**
  74  * Set the MIMETYPE information for the given
  75  * metadata to "application/gnunet-directory".
  76  *
  77  * @param md metadata to add mimetype to
  78  */
  79 void
  80 GNUNET_FS_meta_data_make_directory (struct GNUNET_CONTAINER_MetaData *md)
  81 {
  82   char *mime;
  83
  84   mime =
  85     GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_METATYPE_MIMETYPE);
  86   if (mime != NULL)
  87   {
  88     GNUNET_break (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME));
  89     GNUNET_free (mime);
  90     return;
  91   }
  92   GNUNET_CONTAINER_meta_data_insert (md, "<gnunet>",
  93                                      EXTRACTOR_METATYPE_MIMETYPE,
  94                                      EXTRACTOR_METAFORMAT_UTF8, "text/plain",
  95                                      GNUNET_FS_DIRECTORY_MIME,
  96                                      strlen (GNUNET_FS_DIRECTORY_MIME) + 1);
  97 }
  98
  99
 100 /**
 101  * Closure for 'find_full_data'.
 102  */
 103 struct GetFullDataClosure
 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       GNUNET_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 @a 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 @a data does not represent a directory
 179  */
 180 int
 181 GNUNET_FS_directory_list_contents (size_t size,
 182                                    const void *data,
 183                                    uint64_t offset,
 184                                    GNUNET_FS_DirectoryEntryProcessor dep,
 185                                    void *dep_cls)
 186 {
 187   struct GetFullDataClosure full_data;
 188   const char *cdata = data;
 189   char *emsg;
 190   uint64_t pos;
 191   uint64_t align;
 192   uint32_t mdSize;
 193   uint64_t epos;
 194   struct GNUNET_FS_Uri *uri;
 195   struct GNUNET_CONTAINER_MetaData *md;
 196   char *filename;
 197
 198   if ((offset == 0) &&
 199       ((size < 8 + sizeof(uint32_t)) ||
 200        (0 != memcmp (cdata,
 201                      GNUNET_FS_DIRECTORY_MAGIC,
 202                      8))))
 203     return GNUNET_SYSERR;
 204   pos = offset;
 205   if (offset == 0)
 206   {
 207     GNUNET_memcpy (&mdSize,
 208                    &cdata[8],
 209                    sizeof(uint32_t));
 210     mdSize = ntohl (mdSize);
 211     if (mdSize > size - 8 - sizeof(uint32_t))
 212     {
 213       /* invalid size */
 214       GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 215                   _ ("MAGIC mismatch.  This is not a GNUnet directory.\n"));
 216       return GNUNET_SYSERR;
 217     }
 218     md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[8 + sizeof(uint32_t)],
 219                                                  mdSize);
 220     if (md == NULL)
 221     {
 222       GNUNET_break (0);
 223       return GNUNET_SYSERR;     /* malformed ! */
 224     }
 225     dep (dep_cls,
 226          NULL,
 227          NULL,
 228          md,
 229          0,
 230          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 (NULL == uri)
 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     GNUNET_memcpy (&mdSize,
 276                    &cdata[pos],
 277                    sizeof(uint32_t));
 278     mdSize = ntohl (mdSize);
 279     pos += sizeof(uint32_t);
 280     if (pos + mdSize > size)
 281     {
 282       GNUNET_FS_uri_destroy (uri);
 283       return GNUNET_NO;         /* malformed - or partial download */
 284     }
 285
 286     md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[pos],
 287                                                  mdSize);
 288     if (NULL == md)
 289     {
 290       GNUNET_FS_uri_destroy (uri);
 291       GNUNET_break (0);
 292       return GNUNET_NO;         /* malformed ! */
 293     }
 294     pos += mdSize;
 295     filename =
 296       GNUNET_CONTAINER_meta_data_get_by_type (md,
 297                                               EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME);
 298     full_data.size = 0;
 299     full_data.data = NULL;
 300     GNUNET_CONTAINER_meta_data_iterate (md,
 301                                         &find_full_data,
 302                                         &full_data);
 303     if (NULL != dep)
 304     {
 305       dep (dep_cls,
 306            filename,
 307            uri,
 308            md,
 309            full_data.size,
 310            full_data.data);
 311     }
 312     GNUNET_free_non_null (full_data.data);
 313     GNUNET_free_non_null (filename);
 314     GNUNET_CONTAINER_meta_data_destroy (md);
 315     GNUNET_FS_uri_destroy (uri);
 316   }
 317   return GNUNET_OK;
 318 }
 319
 320
 321 /**
 322  * Entries in the directory (builder).
 323  */
 324 struct BuilderEntry
 325 {
 326   /**
 327    * This is a linked list.
 328    */
 329   struct BuilderEntry *next;
 330
 331   /**
 332    * Length of this entry.
 333    */
 334   size_t len;
 335 };
 336
 337 /**
 338  * Internal state of a directory builder.
 339  */
 340 struct GNUNET_FS_DirectoryBuilder
 341 {
 342   /**
 343    * Meta-data for the directory itself.
 344    */
 345   struct GNUNET_CONTAINER_MetaData *meta;
 346
 347   /**
 348    * Head of linked list of entries.
 349    */
 350   struct BuilderEntry *head;
 351
 352   /**
 353    * Number of entires in the directory.
 354    */
 355   unsigned int count;
 356 };
 357
 358
 359 /**
 360  * Create a directory builder.
 361  *
 362  * @param mdir metadata for the directory
 363  */
 364 struct GNUNET_FS_DirectoryBuilder *
 365 GNUNET_FS_directory_builder_create (const struct GNUNET_CONTAINER_MetaData
 366                                     *mdir)
 367 {
 368   struct GNUNET_FS_DirectoryBuilder *ret;
 369
 370   ret = GNUNET_new (struct GNUNET_FS_DirectoryBuilder);
 371   if (mdir != NULL)
 372     ret->meta = GNUNET_CONTAINER_meta_data_duplicate (mdir);
 373   else
 374     ret->meta = GNUNET_CONTAINER_meta_data_create ();
 375   GNUNET_FS_meta_data_make_directory (ret->meta);
 376   return ret;
 377 }
 378
 379
 380 /**
 381  * Add an entry to a directory.
 382  *
 383  * @param bld directory to extend
 384  * @param uri uri of the entry (must not be a KSK)
 385  * @param md metadata of the entry
 386  * @param data raw data of the entry, can be NULL, otherwise
 387  *        data must point to exactly the number of bytes specified
 388  *        by the uri which must be of type LOC or CHK
 389  */
 390 void
 391 GNUNET_FS_directory_builder_add (struct GNUNET_FS_DirectoryBuilder *bld,
 392                                  const struct GNUNET_FS_Uri *uri,
 393                                  const struct GNUNET_CONTAINER_MetaData *md,
 394                                  const void *data)
 395 {
 396   struct GNUNET_FS_Uri *curi;
 397   struct BuilderEntry *e;
 398   uint64_t fsize;
 399   uint32_t big;
 400   ssize_t ret;
 401   size_t mds;
 402   size_t mdxs;
 403   char *uris;
 404   char *ser;
 405   char *sptr;
 406   size_t slen;
 407   struct GNUNET_CONTAINER_MetaData *meta;
 408   const struct GNUNET_CONTAINER_MetaData *meta_use;
 409
 410   GNUNET_assert (! GNUNET_FS_uri_test_ksk (uri));
 411   if (NULL != data)
 412   {
 413     GNUNET_assert (! GNUNET_FS_uri_test_sks (uri));
 414     if (GNUNET_FS_uri_test_chk (uri))
 415     {
 416       fsize = GNUNET_FS_uri_chk_get_file_size (uri);
 417     }
 418     else
 419     {
 420       curi = GNUNET_FS_uri_loc_get_uri (uri);
 421       GNUNET_assert (NULL != curi);
 422       fsize = GNUNET_FS_uri_chk_get_file_size (curi);
 423       GNUNET_FS_uri_destroy (curi);
 424     }
 425   }
 426   else
 427   {
 428     fsize = 0;                  /* not given */
 429   }
 430   if (fsize > MAX_INLINE_SIZE)
 431     fsize = 0;                  /* too large */
 432   uris = GNUNET_FS_uri_to_string (uri);
 433   slen = strlen (uris) + 1;
 434   mds = GNUNET_CONTAINER_meta_data_get_serialized_size (md);
 435   meta_use = md;
 436   meta = NULL;
 437   if (fsize > 0)
 438   {
 439     meta = GNUNET_CONTAINER_meta_data_duplicate (md);
 440     GNUNET_CONTAINER_meta_data_insert (meta, "<gnunet>",
 441                                        EXTRACTOR_METATYPE_GNUNET_FULL_DATA,
 442                                        EXTRACTOR_METAFORMAT_BINARY, NULL, data,
 443                                        fsize);
 444     mdxs = GNUNET_CONTAINER_meta_data_get_serialized_size (meta);
 445     if ((slen + sizeof(uint32_t) + mdxs - 1) / DBLOCK_SIZE ==
 446         (slen + sizeof(uint32_t) + mds - 1) / DBLOCK_SIZE)
 447     {
 448       /* adding full data would not cause us to cross
 449        * additional blocks, so add it! */
 450       meta_use = meta;
 451       mds = mdxs;
 452     }
 453   }
 454
 455   if (mds > GNUNET_MAX_MALLOC_CHECKED / 2)
 456     mds = GNUNET_MAX_MALLOC_CHECKED / 2;
 457   e = GNUNET_malloc (sizeof(struct BuilderEntry) + slen + mds
 458                      + sizeof(uint32_t));
 459   ser = (char *) &e[1];
 460   GNUNET_memcpy (ser, uris, slen);
 461   GNUNET_free (uris);
 462   sptr = &ser[slen + sizeof(uint32_t)];
 463   ret =
 464     GNUNET_CONTAINER_meta_data_serialize (meta_use, &sptr, mds,
 465                                           GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
 466   if (NULL != meta)
 467     GNUNET_CONTAINER_meta_data_destroy (meta);
 468   if (ret == -1)
 469     mds = 0;
 470   else
 471     mds = ret;
 472   big = htonl (mds);
 473   GNUNET_memcpy (&ser[slen], &big, sizeof(uint32_t));
 474   e->len = slen + sizeof(uint32_t) + mds;
 475   e->next = bld->head;
 476   bld->head = e;
 477   bld->count++;
 478 }
 479
 480
 481 /**
 482  * Given the start and end position of a block of
 483  * data, return the end position of that data
 484  * after alignment to the DBLOCK_SIZE.
 485  */
 486 static size_t
 487 do_align (size_t start_position, size_t end_position)
 488 {
 489   size_t align;
 490
 491   align = (end_position / DBLOCK_SIZE) * DBLOCK_SIZE;
 492   if ((start_position < align) && (end_position > align))
 493     return align + end_position - start_position;
 494   return end_position;
 495 }
 496
 497
 498 /**
 499  * Compute a permuation of the blocks to
 500  * minimize the cost of alignment.  Greedy packer.
 501  *
 502  * @param start starting position for the first block
 503  * @param count size of the two arrays
 504  * @param sizes the sizes of the individual blocks
 505  * @param perm the permutation of the blocks (updated)
 506  */
 507 static void
 508 block_align (size_t start, unsigned int count, const size_t *sizes,
 509              unsigned int *perm)
 510 {
 511   unsigned int i;
 512   unsigned int j;
 513   unsigned int tmp;
 514   unsigned int best;
 515   ssize_t badness;
 516   size_t cpos;
 517   size_t cend;
 518   ssize_t cbad;
 519   unsigned int cval;
 520
 521   cpos = start;
 522   for (i = 0; i < count; i++)
 523   {
 524     start = cpos;
 525     badness = 0x7FFFFFFF;
 526     best = -1;
 527     for (j = i; j < count; j++)
 528     {
 529       cval = perm[j];
 530       cend = cpos + sizes[cval];
 531       if (cpos % DBLOCK_SIZE == 0)
 532       {
 533         /* prefer placing the largest blocks first */
 534         cbad = -(cend % DBLOCK_SIZE);
 535       }
 536       else
 537       {
 538         if (cpos / DBLOCK_SIZE == cend / DBLOCK_SIZE)
 539         {
 540           /* Data fits into the same block! Prefer small left-overs! */
 541           cbad = DBLOCK_SIZE - cend % DBLOCK_SIZE;
 542         }
 543         else
 544         {
 545           /* Would have to waste space to re-align, add big factor, this
 546            * case is a real loss (proportional to space wasted)! */
 547           cbad = DBLOCK_SIZE * (DBLOCK_SIZE - cpos % DBLOCK_SIZE);
 548         }
 549       }
 550       if (cbad < badness)
 551       {
 552         best = j;
 553         badness = cbad;
 554       }
 555     }
 556     GNUNET_assert (best != -1);
 557     tmp = perm[i];
 558     perm[i] = perm[best];
 559     perm[best] = tmp;
 560     cpos += sizes[perm[i]];
 561     cpos = do_align (start, cpos);
 562   }
 563 }
 564
 565
 566 /**
 567  * Finish building the directory.  Frees the
 568  * builder context and returns the directory
 569  * in-memory.
 570  *
 571  * @param bld directory to finish
 572  * @param rsize set to the number of bytes needed
 573  * @param rdata set to the encoded directory
 574  * @return #GNUNET_OK on success
 575  */
 576 int
 577 GNUNET_FS_directory_builder_finish (struct GNUNET_FS_DirectoryBuilder *bld,
 578                                     size_t *rsize,
 579                                     void **rdata)
 580 {
 581   char *data;
 582   char *sptr;
 583   size_t *sizes;
 584   unsigned int *perm;
 585   unsigned int i;
 586   unsigned int j;
 587   struct BuilderEntry *pos;
 588   struct BuilderEntry **bes;
 589   size_t size;
 590   size_t psize;
 591   size_t off;
 592   ssize_t ret;
 593   uint32_t big;
 594
 595   size = strlen (GNUNET_DIRECTORY_MAGIC) + sizeof(uint32_t);
 596   size += GNUNET_CONTAINER_meta_data_get_serialized_size (bld->meta);
 597   sizes = NULL;
 598   perm = NULL;
 599   bes = NULL;
 600   if (0 < bld->count)
 601   {
 602     sizes = GNUNET_new_array (bld->count,
 603                               size_t);
 604     perm = GNUNET_new_array (bld->count,
 605                              unsigned int);
 606     bes = GNUNET_new_array (bld->count,
 607                             struct BuilderEntry *);
 608     pos = bld->head;
 609     for (i = 0; i < bld->count; i++)
 610     {
 611       perm[i] = i;
 612       bes[i] = pos;
 613       sizes[i] = pos->len;
 614       pos = pos->next;
 615     }
 616     block_align (size, bld->count, sizes, perm);
 617     /* compute final size with alignment */
 618     for (i = 0; i < bld->count; i++)
 619     {
 620       psize = size;
 621       size += sizes[perm[i]];
 622       size = do_align (psize, size);
 623     }
 624   }
 625   *rsize = size;
 626   data = GNUNET_malloc_large (size);
 627   if (data == NULL)
 628   {
 629     GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR,
 630                          "malloc");
 631     *rsize = 0;
 632     *rdata = NULL;
 633     GNUNET_free_non_null (sizes);
 634     GNUNET_free_non_null (perm);
 635     GNUNET_free_non_null (bes);
 636     return GNUNET_SYSERR;
 637   }
 638   *rdata = data;
 639   GNUNET_memcpy (data,
 640                  GNUNET_DIRECTORY_MAGIC,
 641                  strlen (GNUNET_DIRECTORY_MAGIC));
 642   off = strlen (GNUNET_DIRECTORY_MAGIC);
 643
 644   sptr = &data[off + sizeof(uint32_t)];
 645   ret =
 646     GNUNET_CONTAINER_meta_data_serialize (bld->meta,
 647                                           &sptr,
 648                                           size - off - sizeof(uint32_t),
 649                                           GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
 650   GNUNET_assert (ret != -1);
 651   big = htonl (ret);
 652   GNUNET_memcpy (&data[off],
 653                  &big,
 654                  sizeof(uint32_t));
 655   off += sizeof(uint32_t) + ret;
 656   for (j = 0; j < bld->count; j++)
 657   {
 658     i = perm[j];
 659     psize = off;
 660     off += sizes[i];
 661     off = do_align (psize, off);
 662     GNUNET_memcpy (&data[off - sizes[i]], &(bes[i])[1], sizes[i]);
 663     GNUNET_free (bes[i]);
 664   }
 665   GNUNET_free_non_null (sizes);
 666   GNUNET_free_non_null (perm);
 667   GNUNET_free_non_null (bes);
 668   GNUNET_assert (off == size);
 669   GNUNET_CONTAINER_meta_data_destroy (bld->meta);
 670   GNUNET_free (bld);
 671   return GNUNET_OK;
 672 }
 673
 674
 675 /* end of fs_directory.c */