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