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  * - add directory builder API to gnunet_fs_service
  29  * - modify directory builder API to support incremental
  30  *   generation of directories (to allow directories that
  31  *   would not fit into memory to be created)
  32  * - modify directory processor API to support incremental
  33  *   iteration over FULL directories (without missing entries)
  34  *   to allow access to directories that do not fit entirely
  35  *   into memory
  36  */
  37 #include "platform.h"
  38 #include "gnunet_fs_service.h"
  39 #include "fs.h"
  40
  41
  42 /**
  43  * Does the meta-data claim that this is a directory?
  44  * Checks if the mime-type is that of a GNUnet directory.
  45  *
  46  * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if
  47  *  we have no mime-type information (treat as 'GNUNET_NO')
  48  */
  49 int
  50 GNUNET_FS_meta_data_test_for_directory (const struct GNUNET_CONTAINER_MetaData *md)
  51 {
  52   char *mime;
  53   int ret;
  54
  55   mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
  56   if (mime == NULL)
  57     return GNUNET_SYSERR;
  58   ret = (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME)) ? GNUNET_YES : GNUNET_NO;
  59   GNUNET_free (mime);
  60   return ret;
  61 }
  62
  63
  64 /**
  65  * Set the MIMETYPE information for the given
  66  * metadata to "application/gnunet-directory".
  67  *
  68  * @param md metadata to add mimetype to
  69  */
  70 void
  71 GNUNET_FS_meta_data_make_directory (struct GNUNET_CONTAINER_MetaData *md)
  72 {
  73   char *mime;
  74
  75   mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
  76   if (mime != NULL)
  77     {
  78       GNUNET_break (0 == strcmp (mime,
  79                                  GNUNET_FS_DIRECTORY_MIME));
  80       GNUNET_free (mime);
  81       return;
  82     }
  83   GNUNET_CONTAINER_meta_data_insert (md,
  84                                      EXTRACTOR_MIMETYPE,
  85                                      GNUNET_FS_DIRECTORY_MIME);
  86 }
  87
  88
  89 /**
  90  * Iterate over all entries in a directory.  Note that directories
  91  * are structured such that it is possible to iterate over the
  92  * individual blocks as well as over the entire directory.  Thus
  93  * a client can call this function on the buffer in the
  94  * GNUNET_FS_ProgressCallback.  Also, directories can optionally
  95  * include the contents of (small) files embedded in the directory
  96  * itself; for those files, the processor may be given the
  97  * contents of the file directly by this function.
  98  * <p>
  99  *
 100  * Note that this function maybe called on parts of directories.  Thus
 101  * parser errors should not be reported _at all_ (with GNUNET_break).
 102  * Still, if some entries can be recovered despite these parsing
 103  * errors, the function should try to do this.
 104  *
 105  * @param size number of bytes in data
 106  * @param data pointer to the beginning of the directory
 107  * @param offset offset of data in the directory
 108  * @param dep function to call on each entry
 109  * @param dep_cls closure for dep
 110  */
 111 void
 112 GNUNET_FS_directory_list_contents (size_t size,
 113                                    const void *data,
 114                                    uint64_t offset,
 115                                    GNUNET_FS_DirectoryEntryProcessor dep,
 116                                    void *dep_cls)
 117 {
 118   const char *cdata = data;
 119   char *emsg;
 120   uint64_t pos;
 121   uint64_t align;
 122   uint32_t mdSize;
 123   uint64_t epos;
 124   struct GNUNET_FS_Uri *uri;
 125   struct GNUNET_CONTAINER_MetaData *md;
 126   char *filename;
 127
 128   pos = offset;
 129   if ( (pos == 0) &&
 130        (size >= 8 + sizeof (uint32_t)) &&
 131        (0 == memcmp (cdata, GNUNET_FS_DIRECTORY_MAGIC, 8)) )
 132     {
 133       memcpy (&mdSize, &cdata[8], sizeof (uint32_t));
 134       mdSize = ntohl (mdSize);
 135       if (mdSize > size - 8 - sizeof (uint32_t))
 136         {
 137           /* invalid size */
 138           GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 139                       _("Not a GNUnet directory.\n"));
 140           return;
 141         }
 142       md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[8 +
 143                                                          sizeof (uint32_t)],
 144                                                    mdSize);
 145       if (md == NULL)
 146         {
 147           GNUNET_break (0);
 148           return; /* malformed ! */
 149         }
 150       dep (dep_cls,
 151            NULL,
 152            NULL,
 153            md,
 154            0,
 155            NULL);
 156       GNUNET_CONTAINER_meta_data_destroy (md);
 157       pos = 8 + sizeof (uint32_t) + mdSize;
 158     }
 159   while (pos < size)
 160     {
 161       /* find end of URI */
 162       if (cdata[pos] == '\0')
 163         {
 164           /* URI is never empty, must be end of block,
 165              skip to next alignment */
 166           align =
 167             ((pos / GNUNET_FS_DBLOCK_SIZE) + 1) * GNUNET_FS_DBLOCK_SIZE;
 168           if (align == pos)
 169             {
 170               /* if we were already aligned, still skip a block! */
 171               align += GNUNET_FS_DBLOCK_SIZE;
 172             }
 173           pos = align;
 174           if (pos >= size)
 175             {
 176               /* malformed - or partial download... */
 177               break;
 178             }
 179         }
 180       epos = pos;
 181       while ((epos < size) && (cdata[epos] != '\0'))
 182         epos++;
 183       if (epos >= size)
 184         return;   /* malformed - or partial download */
 185
 186       uri = GNUNET_FS_uri_parse (&cdata[pos], &emsg);
 187       pos = epos + 1;
 188       if (uri == NULL)
 189         {
 190           GNUNET_free (emsg);
 191           pos--;                /* go back to '\0' to force going to next alignment */
 192           continue;
 193         }
 194       if (GNUNET_FS_uri_test_ksk (uri))
 195         {
 196           GNUNET_FS_uri_destroy (uri);
 197           GNUNET_break (0);
 198           return; /* illegal in directory! */
 199         }
 200
 201       memcpy (&mdSize, &cdata[pos], sizeof (uint32_t));
 202       mdSize = ntohl (mdSize);
 203       pos += sizeof (uint32_t);
 204       if (pos + mdSize > size)
 205         {
 206           GNUNET_FS_uri_destroy (uri);
 207           return; /* malformed - or partial download */
 208         }
 209
 210       md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[pos], mdSize);
 211       if (md == NULL)
 212         {
 213           GNUNET_FS_uri_destroy (uri);
 214           GNUNET_break (0);
 215           return; /* malformed ! */
 216         }
 217       pos += mdSize;
 218       /* FIXME: add support for embedded data */
 219       filename = GNUNET_CONTAINER_meta_data_get_by_type (md,
 220                                                          EXTRACTOR_FILENAME);
 221       if (dep != NULL)
 222          dep (dep_cls,
 223               filename,
 224               uri,
 225               md,
 226               0,
 227               NULL);
 228       GNUNET_free_non_null (filename);
 229       GNUNET_CONTAINER_meta_data_destroy (md);
 230       GNUNET_FS_uri_destroy (uri);
 231     }
 232 }
 233
 234
 235 void
 236 GNUNET_FS_directory_create ()
 237 {
 238 }
 239
 240
 241 #if 0
 242
 243
 244 /**
 245  * Given the start and end position of a block of
 246  * data, return the end position of that data
 247  * after alignment to the GNUNET_FS_DBLOCK_SIZE.
 248  */
 249 static uint64_t
 250 do_align (uint64_t start_position,
 251           uint64_t end_position)
 252 {
 253   uint64_t align;
 254
 255   align = (end_position / GNUNET_FS_DBLOCK_SIZE) * GNUNET_FS_DBLOCK_SIZE;
 256   if ((start_position < align) && (end_position > align))
 257     return align + end_position - start_position;
 258   return end_position;
 259 }
 260
 261
 262 /**
 263  * Compute a permuation of the blocks to
 264  * minimize the cost of alignment.  Greedy packer.
 265  *
 266  * @param start starting position for the first block
 267  * @param count size of the two arrays
 268  * @param sizes the sizes of the individual blocks
 269  * @param perm the permutation of the blocks (updated)
 270  */
 271 static void
 272 block_align (uint64_t start,
 273              unsigned int count,
 274              const uint64_t *sizes,
 275              unsigned int *perm)
 276 {
 277   unsigned int i;
 278   unsigned int j;
 279   unsigned int tmp;
 280   unsigned int best;
 281   int64_t badness;
 282   uint64_t cpos;
 283   uint64_t cend;
 284   int64_t cbad;
 285   unsigned int cval;
 286
 287   cpos = start;
 288   for (i = 0; i < count; i++)
 289     {
 290       start = cpos;
 291       badness = 0x7FFFFFFF;
 292       best = -1;
 293       for (j = i; j < count; j++)
 294         {
 295           cval = perm[j];
 296           cend = cpos + sizes[cval];
 297           if (cpos % GNUNET_FS_DBLOCK_SIZE == 0)
 298             {
 299               /* prefer placing the largest blocks first */
 300               cbad = -(cend % GNUNET_FS_DBLOCK_SIZE);
 301             }
 302           else
 303             {
 304               if (cpos / GNUNET_FS_DBLOCK_SIZE ==
 305                   cend / GNUNET_FS_DBLOCK_SIZE)
 306                 {
 307                   /* Data fits into the same block! Prefer small left-overs! */
 308                   cbad =
 309                     GNUNET_FS_DBLOCK_SIZE - cend % GNUNET_FS_DBLOCK_SIZE;
 310                 }
 311               else
 312                 {
 313                   /* Would have to waste space to re-align, add big factor, this
 314                      case is a real loss (proportional to space wasted)! */
 315                   cbad =
 316                     GNUNET_FS_DBLOCK_SIZE * (GNUNET_FS_DBLOCK_SIZE -
 317                                              cpos %
 318                                              GNUNET_FS_DBLOCK_SIZE);
 319                 }
 320             }
 321           if (cbad < badness)
 322             {
 323               best = j;
 324               badness = cbad;
 325             }
 326         }
 327       tmp = perm[i];
 328       perm[i] = perm[best];
 329       perm[best] = tmp;
 330       cpos += sizes[perm[i]];
 331       cpos = do_align (start, cpos);
 332     }
 333 }
 334
 335
 336 /**
 337  * Create a directory.  We allow packing more than one variable
 338  * size entry into one block (and an entry could also span more
 339  * than one block), but an entry that is smaller than a single
 340  * block will never cross the block boundary.  This is done to
 341  * allow processing entries of a directory already even if the
 342  * download is still partial.<p>
 343  *
 344  * The first block begins with the directories MAGIC signature,
 345  * followed by the meta-data about the directory itself.<p>
 346  *
 347  * After that, the directory consists of block-aligned pairs
 348  * of URIs (0-terminated strings) and serialized meta-data.
 349  *
 350  * @param data pointer set to the beginning of the directory
 351  * @param len set to number of bytes in data
 352  * @param count number of entries in uris and mds
 353  * @param uris URIs of the files in the directory
 354  * @param mds meta-data for the files (must match
 355  *        respective values at same offset in in uris)
 356  * @param mdir meta-data for the directory
 357  * @return GNUNET_OK on success, GNUNET_SYSERR on error
 358  */
 359 int
 360 GNUNET_FS_directory_create (char **data,
 361                             size_t *len,
 362                             unsigned int count,
 363                             const struct GNUNET_FS_Uri **uris,
 364                             const struct GNUNET_CONTAINER_MetaData **mds,
 365                             const struct GNUNET_CONTAINER_MetaData *mdir)
 366 {
 367   unsigned int i;
 368   unsigned int j;
 369   uint64_t psize;
 370   uint64_t size;
 371   uint64_t pos;
 372   char **ucs;
 373   int ret;
 374   uint64_t *sizes;
 375   unsigned int *perm;
 376
 377   for (i = 0; i < count; i++)
 378     {
 379       if (GNUNET_FS_uri_test_ksk (fis[i].uri))
 380         {
 381           GNUNET_break (0);
 382           return GNUNET_SYSERR; /* illegal in directory! */
 383         }
 384     }
 385   ucs = GNUNET_malloc (sizeof (char *) * count);
 386   size = 8 + sizeof (unsigned int);
 387   size += GNUNET_meta_data_get_serialized_size (meta, GNUNET_SERIALIZE_FULL);
 388   sizes = GNUNET_malloc (count * sizeof (unsigned long long));
 389   perm = GNUNET_malloc (count * sizeof (int));
 390   for (i = 0; i < count; i++)
 391     {
 392       perm[i] = i;
 393       ucs[i] = GNUNET_FS_uri_to_string (fis[i].uri);
 394       GNUNET_assert (ucs[i] != NULL);
 395       psize =
 396         GNUNET_meta_data_get_serialized_size (fis[i].meta,
 397                                               GNUNET_SERIALIZE_FULL);
 398       if (psize == -1)
 399         {
 400           GNUNET_break (0);
 401           GNUNET_free (sizes);
 402           GNUNET_free (perm);
 403           while (i >= 0)
 404             GNUNET_free (ucs[i--]);
 405           GNUNET_free (ucs);
 406           return GNUNET_SYSERR;
 407         }
 408       sizes[i] = psize + sizeof (unsigned int) + strlen (ucs[i]) + 1;
 409     }
 410   /* permutate entries to minimize alignment cost */
 411   block_align (size, count, sizes, perm);
 412
 413   /* compute final size with alignment */
 414   for (i = 0; i < count; i++)
 415     {
 416       psize = size;
 417       size += sizes[perm[i]];
 418       size = do_align (psize, size);
 419     }
 420   *len = size;
 421   *data = GNUNET_malloc (size);
 422   memset (*data, 0, size);
 423
 424   pos = 8;
 425   memcpy (*data, GNUNET_DIRECTORY_MAGIC, 8);
 426
 427   ret = GNUNET_CONTAINER_meta_data_serialize (meta,
 428                                               &(*data)[pos +
 429                                                        sizeof (unsigned int)],
 430                                               size - pos - sizeof (unsigned int),
 431                                               GNUNET_SERIALIZE_FULL);
 432   GNUNET_assert (ret != GNUNET_SYSERR);
 433   ret = htonl (ret);
 434   memcpy (&(*data)[pos], &ret, sizeof (unsigned int));
 435   pos += ntohl (ret) + sizeof (unsigned int);
 436
 437   for (j = 0; j < count; j++)
 438     {
 439       i = perm[j];
 440       psize = pos;
 441       pos += sizes[i];
 442       pos = do_align (psize, pos);
 443       pos -= sizes[i];          /* go back to beginning */
 444       memcpy (&(*data)[pos], ucs[i], strlen (ucs[i]) + 1);
 445       pos += strlen (ucs[i]) + 1;
 446       GNUNET_free (ucs[i]);
 447       ret = GNUNET_CONTAINER_meta_data_serialize (mds[i],
 448                                                   &(*data)[pos +
 449                                                            sizeof (unsigned int)],
 450                                                   size - pos -
 451                                                   sizeof (unsigned int),
 452                                                   GNUNET_SERIALIZE_FULL);
 453       GNUNET_assert (ret != GNUNET_SYSERR);
 454       ret = htonl (ret);
 455       memcpy (&(*data)[pos], &ret, sizeof (unsigned int));
 456       pos += ntohl (ret) + sizeof (unsigned int);
 457     }
 458   GNUNET_free (sizes);
 459   GNUNET_free (perm);
 460   GNUNET_free (ucs);
 461   GNUNET_assert (pos == size);
 462   return GNUNET_OK;
 463 }
 464
 465
 466 #endif
 467
 468 /* end of fs_directory.c */