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