d67c6e8efadc463abbb8e0d133b717a372fa71bf
[oweals/gnunet.git] / 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 #ifndef EXTRACTOR_GNUNET_FULL_DATA
40 #define EXTRACTOR_GNUNET_FULL_DATA 137
41 #endif
42
43 /**
44  * String that is used to indicate that a file
45  * is a GNUnet directory.
46  */
47 #define GNUNET_DIRECTORY_MAGIC "\211GND\r\n\032\n"
48
49
50 /**
51  * Does the meta-data claim that this is a directory?
52  * Checks if the mime-type is that of a GNUnet directory.
53  *
54  * @return GNUNET_YES if it is, GNUNET_NO if it is not, GNUNET_SYSERR if
55  *  we have no mime-type information (treat as 'GNUNET_NO')
56  */
57 int 
58 GNUNET_FS_meta_data_test_for_directory (const struct GNUNET_CONTAINER_MetaData *md)
59 {
60   char *mime;
61   int ret;
62   
63   mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
64   if (mime == NULL)
65     return GNUNET_SYSERR;
66   ret = (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME)) ? GNUNET_YES : GNUNET_NO;
67   GNUNET_free (mime);
68   return ret; 
69 }
70
71
72 /**
73  * Set the MIMETYPE information for the given
74  * metadata to "application/gnunet-directory".
75  * 
76  * @param md metadata to add mimetype to
77  */
78 void
79 GNUNET_FS_meta_data_make_directory (struct GNUNET_CONTAINER_MetaData *md)
80 {
81   char *mime;
82   
83   mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
84   if (mime != NULL)
85     {
86       GNUNET_break (0 == strcmp (mime,
87                                  GNUNET_FS_DIRECTORY_MIME));
88       GNUNET_free (mime);
89       return;
90     }
91   GNUNET_CONTAINER_meta_data_insert (md, 
92                                      EXTRACTOR_MIMETYPE,
93                                      GNUNET_FS_DIRECTORY_MIME);
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_FILENAME);
229       file_data = GNUNET_CONTAINER_meta_data_get_by_type (md,
230                                                           EXTRACTOR_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   ret->meta = GNUNET_CONTAINER_meta_data_duplicate (mdir);
295   GNUNET_FS_meta_data_make_directory (ret->meta);
296   return ret;
297 }
298
299
300 /**
301  * Add an entry to a directory.
302  * 
303  * @param bld directory to extend
304  * @param uri uri of the entry (must not be a KSK)
305  * @param md metadata of the entry
306  * @param data raw data of the entry, can be NULL, otherwise
307  *        data must point to exactly the number of bytes specified
308  *        by the uri which must be of type LOC or CHK
309  */
310 void
311 GNUNET_FS_directory_builder_add (struct GNUNET_FS_DirectoryBuilder *bld,
312                                  const struct GNUNET_FS_Uri *uri,
313                                  const struct GNUNET_CONTAINER_MetaData *md,
314                                  const void *data)
315 {
316   struct BuilderEntry *e;
317   uint64_t fsize;
318   uint32_t big;
319   ssize_t ret;
320   size_t mds;
321   size_t mdxs;
322   char *uris;
323   char *ser;
324   size_t slen;
325   struct GNUNET_CONTAINER_MetaData *meta;
326   const struct GNUNET_CONTAINER_MetaData *meta_use;
327
328   GNUNET_assert (! GNUNET_FS_uri_test_ksk (uri));
329   if (NULL != data)
330     if (GNUNET_FS_uri_test_chk (uri))
331       fsize = GNUNET_FS_uri_chk_get_file_size (uri);
332     else
333       fsize = GNUNET_FS_uri_chk_get_file_size (GNUNET_FS_uri_loc_get_uri (uri));
334   else
335     fsize = 0; /* not given */
336   if (fsize > MAX_INLINE_SIZE)
337     fsize = 0; /* too large */
338   if (NULL != memchr (data, 0, fsize))
339     fsize = 0; /* must not have 0's in data! */
340   uris = GNUNET_FS_uri_to_string (uri);
341   slen = strlen (uris) + 1;
342   mds =
343     GNUNET_CONTAINER_meta_data_get_serialized_size (md,
344                                                     GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);  
345   meta_use = md;
346   meta = NULL;
347   if (fsize > 0)
348     {
349       meta = GNUNET_CONTAINER_meta_data_duplicate (md);
350       GNUNET_CONTAINER_meta_data_insert (meta,
351                                          EXTRACTOR_GNUNET_FULL_DATA,
352                                          data);
353       mdxs =
354         GNUNET_CONTAINER_meta_data_get_serialized_size (meta,
355                                                         GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);  
356       if ( (slen + sizeof (uint32_t) + mdxs - 1) / DBLOCK_SIZE ==
357            (slen + sizeof (uint32_t) + mds - 1) / DBLOCK_SIZE)
358         {
359           /* adding full data would not cause us to cross
360              additional blocks, so add it! */
361           meta_use = meta;
362           mds = mdxs;
363         }
364     }
365
366   if (mds > GNUNET_MAX_MALLOC_CHECKED / 2)
367     mds = GNUNET_MAX_MALLOC_CHECKED / 2;
368   e = GNUNET_malloc (sizeof(struct BuilderEntry) + 
369                      slen + mds + sizeof (uint32_t));
370   ser = (char*) &e[1];
371   memcpy (ser, uris, slen);
372   GNUNET_free (uris);
373   ret = GNUNET_CONTAINER_meta_data_serialize (meta_use,
374                                               &ser[slen + sizeof(uint32_t)],
375                                               mds,
376                                               GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
377   if (NULL != meta)
378     GNUNET_CONTAINER_meta_data_destroy (meta);
379   if (ret == -1)
380     mds = 0;
381   else
382     mds = ret;
383   big = htonl (mds);
384   memcpy (&ser[slen], &big, sizeof (uint32_t));
385   e->len = slen + sizeof (uint32_t) + mds;
386   e->next = bld->head;
387   bld->head = e;
388   bld->count++;
389 }
390
391
392 /**
393  * Given the start and end position of a block of
394  * data, return the end position of that data
395  * after alignment to the DBLOCK_SIZE.
396  */
397 static size_t
398 do_align (size_t start_position, 
399           size_t end_position)
400 {
401   size_t align;
402   
403   align = (end_position / DBLOCK_SIZE) * DBLOCK_SIZE;
404   if ((start_position < align) && (end_position > align))
405     return align + end_position - start_position;
406   return end_position;
407 }
408
409
410 /**
411  * Compute a permuation of the blocks to
412  * minimize the cost of alignment.  Greedy packer.
413  *
414  * @param start starting position for the first block
415  * @param count size of the two arrays
416  * @param sizes the sizes of the individual blocks
417  * @param perm the permutation of the blocks (updated)
418  */
419 static void
420 block_align (size_t start,
421              unsigned int count, 
422              const size_t *sizes,
423              unsigned int *perm)
424 {
425   unsigned int i;
426   unsigned int j;
427   unsigned int tmp;
428   unsigned int best;
429   ssize_t badness;
430   size_t cpos;
431   size_t cend;
432   ssize_t cbad;
433   unsigned int cval;
434
435   cpos = start;
436   for (i = 0; i < count; i++)
437     {
438       start = cpos;
439       badness = 0x7FFFFFFF;
440       best = -1;
441       for (j = i; j < count; j++)
442         {
443           cval = perm[j];
444           cend = cpos + sizes[cval];
445           if (cpos % DBLOCK_SIZE == 0)
446             {
447               /* prefer placing the largest blocks first */
448               cbad = -(cend % DBLOCK_SIZE);
449             }
450           else
451             {
452               if (cpos / DBLOCK_SIZE ==
453                   cend / DBLOCK_SIZE)
454                 {
455                   /* Data fits into the same block! Prefer small left-overs! */
456                   cbad =
457                     DBLOCK_SIZE - cend % DBLOCK_SIZE;
458                 }
459               else
460                 {
461                   /* Would have to waste space to re-align, add big factor, this
462                      case is a real loss (proportional to space wasted)! */
463                   cbad =
464                     DBLOCK_SIZE * (DBLOCK_SIZE -
465                                              cpos %
466                                              DBLOCK_SIZE);
467                 }
468             }
469           if (cbad < badness)
470             {
471               best = j;
472               badness = cbad;
473             }
474         }
475       tmp = perm[i];
476       perm[i] = perm[best];
477       perm[best] = tmp;
478       cpos += sizes[perm[i]];
479       cpos = do_align (start, cpos);
480     }
481 }
482
483
484 /**
485  * Finish building the directory.  Frees the
486  * builder context and returns the directory
487  * in-memory.
488  *
489  * @param bld directory to finish
490  * @param rsize set to the number of bytes needed
491  * @param rdata set to the encoded directory
492  */
493 void
494 GNUNET_FS_directory_builder_finish (struct GNUNET_FS_DirectoryBuilder *bld,
495                                     size_t *rsize,
496                                     void **rdata)
497 {
498   char *data;
499   size_t *sizes;
500   unsigned int *perm;
501   unsigned int i;
502   unsigned int j;
503   struct BuilderEntry *pos;
504   struct BuilderEntry **bes;
505   size_t size;
506   size_t psize;
507   size_t off;
508   ssize_t ret;
509   uint32_t big;
510
511   size = 8 + sizeof (uint32_t);
512   size += GNUNET_CONTAINER_meta_data_get_serialized_size (bld->meta, 
513                                                           GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
514   if (bld->count > 0)
515     {
516       sizes = GNUNET_malloc (bld->count * sizeof (size_t));
517       perm = GNUNET_malloc (bld->count * sizeof (unsigned int));
518       bes = GNUNET_malloc (bld->count * sizeof (struct BuilderEntry *));
519       pos = bld->head;
520       for (i = 0; i < bld->count; i++)
521         {
522           perm[i] = i;
523           bes[i] = pos;
524           sizes[i] = pos->len;
525           pos = pos->next;
526         }
527     }  
528   block_align (size,
529                bld->count,
530                sizes,
531                perm);
532
533   /* compute final size with alignment */
534   for (i = 0; i < bld->count; i++)
535     {
536       psize = size;
537       size += sizes[perm[i]];
538       size = do_align (psize, size);
539     }
540   *rsize = size;
541   data = GNUNET_malloc (size);
542   *rdata = data;
543   memcpy (data, GNUNET_DIRECTORY_MAGIC, 8);
544   off = 8;
545
546   ret = GNUNET_CONTAINER_meta_data_serialize (bld->meta,
547                                               &data[off +
548                                                     sizeof (uint32_t)],
549                                               size - off - sizeof (uint32_t),
550                                               GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
551   GNUNET_assert (ret != -1);
552   big = htonl (ret);  
553   memcpy (&data[8], &big, sizeof (uint32_t));
554   off += sizeof (uint32_t) + ret;
555   for (j = 0; j < bld->count; j++)
556     {
557       i = perm[j];
558       psize = off;
559       off += sizes[i];
560       off = do_align (psize, off);
561       memcpy (&data[off - sizes[i]], 
562               &(bes[i])[1],
563               sizes[i]);
564       GNUNET_free (bes[i]);
565     }
566   GNUNET_free (sizes);
567   GNUNET_free (perm);
568   GNUNET_free (bes);
569   GNUNET_assert (off == size);  
570   GNUNET_CONTAINER_meta_data_destroy (bld->meta);
571   GNUNET_free (bld);
572 }
573
574
575 /* end of fs_directory.c */