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