2 This file is part of GNUnet.
3 (C) 2003, 2004, 2006, 2009 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file fs/fs_directory.c
23 * @brief Helper functions for building directories.
24 * @author Christian Grothoff
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
36 #include "gnunet_fs_service.h"
39 #ifndef EXTRACTOR_GNUNET_FULL_DATA
40 #define EXTRACTOR_GNUNET_FULL_DATA 137
44 * String that is used to indicate that a file
45 * is a GNUnet directory.
47 #define GNUNET_DIRECTORY_MAGIC "\211GND\r\n\032\n"
51 * Does the meta-data claim that this is a directory?
52 * Checks if the mime-type is that of a GNUnet directory.
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')
58 GNUNET_FS_meta_data_test_for_directory (const struct GNUNET_CONTAINER_MetaData *md)
63 mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
66 ret = (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME)) ? GNUNET_YES : GNUNET_NO;
73 * Set the MIMETYPE information for the given
74 * metadata to "application/gnunet-directory".
76 * @param md metadata to add mimetype to
79 GNUNET_FS_meta_data_make_directory (struct GNUNET_CONTAINER_MetaData *md)
83 mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
86 GNUNET_break (0 == strcmp (mime,
87 GNUNET_FS_DIRECTORY_MIME));
91 GNUNET_CONTAINER_meta_data_insert (md,
93 GNUNET_FS_DIRECTORY_MIME);
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.
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.
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
120 GNUNET_FS_directory_list_contents (size_t size,
123 GNUNET_FS_DirectoryEntryProcessor dep,
126 const char *cdata = data;
133 struct GNUNET_FS_Uri *uri;
134 struct GNUNET_CONTAINER_MetaData *md;
139 (size >= 8 + sizeof (uint32_t)) &&
140 (0 == memcmp (cdata, GNUNET_FS_DIRECTORY_MAGIC, 8)) )
142 memcpy (&mdSize, &cdata[8], sizeof (uint32_t));
143 mdSize = ntohl (mdSize);
144 if (mdSize > size - 8 - sizeof (uint32_t))
147 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
148 _("Not a GNUnet directory.\n"));
151 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[8 +
157 return; /* malformed ! */
165 GNUNET_CONTAINER_meta_data_destroy (md);
166 pos = 8 + sizeof (uint32_t) + mdSize;
170 /* find end of URI */
171 if (cdata[pos] == '\0')
173 /* URI is never empty, must be end of block,
174 skip to next alignment */
176 ((pos / DBLOCK_SIZE) + 1) * DBLOCK_SIZE;
179 /* if we were already aligned, still skip a block! */
180 align += DBLOCK_SIZE;
185 /* malformed - or partial download... */
190 while ((epos < size) && (cdata[epos] != '\0'))
193 return; /* malformed - or partial download */
195 uri = GNUNET_FS_uri_parse (&cdata[pos], &emsg);
200 pos--; /* go back to '\0' to force going to next alignment */
203 if (GNUNET_FS_uri_test_ksk (uri))
205 GNUNET_FS_uri_destroy (uri);
207 return; /* illegal in directory! */
210 memcpy (&mdSize, &cdata[pos], sizeof (uint32_t));
211 mdSize = ntohl (mdSize);
212 pos += sizeof (uint32_t);
213 if (pos + mdSize > size)
215 GNUNET_FS_uri_destroy (uri);
216 return; /* malformed - or partial download */
219 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[pos], mdSize);
222 GNUNET_FS_uri_destroy (uri);
224 return; /* malformed ! */
227 filename = GNUNET_CONTAINER_meta_data_get_by_type (md,
229 file_data = GNUNET_CONTAINER_meta_data_get_by_type (md,
230 EXTRACTOR_GNUNET_FULL_DATA);
236 (file_data != NULL) ? strlen(file_data) : 0,
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);
246 * Entries in the directory (builder).
251 * This is a linked list.
253 struct BuilderEntry *next;
256 * Length of this entry.
262 * Internal state of a directory builder.
264 struct GNUNET_FS_DirectoryBuilder
267 * Meta-data for the directory itself.
269 struct GNUNET_CONTAINER_MetaData *meta;
272 * Head of linked list of entries.
274 struct BuilderEntry *head;
277 * Number of entires in the directory.
284 * Create a directory builder.
286 * @param mdir metadata for the directory
288 struct GNUNET_FS_DirectoryBuilder *
289 GNUNET_FS_directory_builder_create (const struct GNUNET_CONTAINER_MetaData *mdir)
291 struct GNUNET_FS_DirectoryBuilder *ret;
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);
301 * Add an entry to a directory.
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
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,
316 struct GNUNET_FS_Uri *curi;
317 struct BuilderEntry *e;
326 struct GNUNET_CONTAINER_MetaData *meta;
327 const struct GNUNET_CONTAINER_MetaData *meta_use;
329 GNUNET_assert (! GNUNET_FS_uri_test_ksk (uri));
331 if (GNUNET_FS_uri_test_chk (uri))
332 fsize = GNUNET_FS_uri_chk_get_file_size (uri);
335 curi = GNUNET_FS_uri_loc_get_uri (uri);
336 fsize = GNUNET_FS_uri_chk_get_file_size (curi);
337 GNUNET_FS_uri_destroy (curi);
340 fsize = 0; /* not given */
341 if (fsize > MAX_INLINE_SIZE)
342 fsize = 0; /* too large */
343 if ( (NULL == data) ||
344 (NULL != memchr (data, 0, fsize)) )
345 fsize = 0; /* must not have 0's in data! */
346 uris = GNUNET_FS_uri_to_string (uri);
347 slen = strlen (uris) + 1;
349 GNUNET_CONTAINER_meta_data_get_serialized_size (md,
350 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
355 meta = GNUNET_CONTAINER_meta_data_duplicate (md);
356 GNUNET_CONTAINER_meta_data_insert (meta,
357 EXTRACTOR_GNUNET_FULL_DATA,
360 GNUNET_CONTAINER_meta_data_get_serialized_size (meta,
361 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
362 if ( (slen + sizeof (uint32_t) + mdxs - 1) / DBLOCK_SIZE ==
363 (slen + sizeof (uint32_t) + mds - 1) / DBLOCK_SIZE)
365 /* adding full data would not cause us to cross
366 additional blocks, so add it! */
372 if (mds > GNUNET_MAX_MALLOC_CHECKED / 2)
373 mds = GNUNET_MAX_MALLOC_CHECKED / 2;
374 e = GNUNET_malloc (sizeof(struct BuilderEntry) +
375 slen + mds + sizeof (uint32_t));
377 memcpy (ser, uris, slen);
379 ret = GNUNET_CONTAINER_meta_data_serialize (meta_use,
380 &ser[slen + sizeof(uint32_t)],
382 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
384 GNUNET_CONTAINER_meta_data_destroy (meta);
390 memcpy (&ser[slen], &big, sizeof (uint32_t));
391 e->len = slen + sizeof (uint32_t) + mds;
399 * Given the start and end position of a block of
400 * data, return the end position of that data
401 * after alignment to the DBLOCK_SIZE.
404 do_align (size_t start_position,
409 align = (end_position / DBLOCK_SIZE) * DBLOCK_SIZE;
410 if ((start_position < align) && (end_position > align))
411 return align + end_position - start_position;
417 * Compute a permuation of the blocks to
418 * minimize the cost of alignment. Greedy packer.
420 * @param start starting position for the first block
421 * @param count size of the two arrays
422 * @param sizes the sizes of the individual blocks
423 * @param perm the permutation of the blocks (updated)
426 block_align (size_t start,
442 for (i = 0; i < count; i++)
445 badness = 0x7FFFFFFF;
447 for (j = i; j < count; j++)
450 cend = cpos + sizes[cval];
451 if (cpos % DBLOCK_SIZE == 0)
453 /* prefer placing the largest blocks first */
454 cbad = -(cend % DBLOCK_SIZE);
458 if (cpos / DBLOCK_SIZE ==
461 /* Data fits into the same block! Prefer small left-overs! */
463 DBLOCK_SIZE - cend % DBLOCK_SIZE;
467 /* Would have to waste space to re-align, add big factor, this
468 case is a real loss (proportional to space wasted)! */
470 DBLOCK_SIZE * (DBLOCK_SIZE -
482 perm[i] = perm[best];
484 cpos += sizes[perm[i]];
485 cpos = do_align (start, cpos);
491 * Finish building the directory. Frees the
492 * builder context and returns the directory
495 * @param bld directory to finish
496 * @param rsize set to the number of bytes needed
497 * @param rdata set to the encoded directory
498 * @return GNUNET_OK on success
501 GNUNET_FS_directory_builder_finish (struct GNUNET_FS_DirectoryBuilder *bld,
510 struct BuilderEntry *pos;
511 struct BuilderEntry **bes;
518 size = 8 + sizeof (uint32_t);
519 size += GNUNET_CONTAINER_meta_data_get_serialized_size (bld->meta,
520 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
526 sizes = GNUNET_malloc (bld->count * sizeof (size_t));
527 perm = GNUNET_malloc (bld->count * sizeof (unsigned int));
528 bes = GNUNET_malloc (bld->count * sizeof (struct BuilderEntry *));
530 for (i = 0; i < bld->count; i++)
541 /* compute final size with alignment */
542 for (i = 0; i < bld->count; i++)
545 size += sizes[perm[i]];
546 size = do_align (psize, size);
550 data = GNUNET_malloc_large (size);
553 GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR,
557 return GNUNET_SYSERR;
560 memcpy (data, GNUNET_DIRECTORY_MAGIC, 8);
563 ret = GNUNET_CONTAINER_meta_data_serialize (bld->meta,
566 size - off - sizeof (uint32_t),
567 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
568 GNUNET_assert (ret != -1);
570 memcpy (&data[8], &big, sizeof (uint32_t));
571 off += sizeof (uint32_t) + ret;
572 for (j = 0; j < bld->count; j++)
577 off = do_align (psize, off);
578 memcpy (&data[off - sizes[i]],
581 GNUNET_free (bes[i]);
583 GNUNET_free_non_null (sizes);
584 GNUNET_free_non_null (perm);
585 GNUNET_free_non_null (bes);
586 GNUNET_assert (off == size);
587 GNUNET_CONTAINER_meta_data_destroy (bld->meta);
593 /* end of fs_directory.c */