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