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 * - 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
38 #include "gnunet_fs_service.h"
43 * Does the meta-data claim that this is a directory?
44 * Checks if the mime-type is that of a GNUnet directory.
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')
50 GNUNET_FS_meta_data_test_for_directory (const struct GNUNET_CONTAINER_MetaData *md)
55 mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
58 ret = (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME)) ? GNUNET_YES : GNUNET_NO;
65 * Set the MIMETYPE information for the given
66 * metadata to "application/gnunet-directory".
68 * @param md metadata to add mimetype to
71 GNUNET_FS_meta_data_make_directory (struct GNUNET_CONTAINER_MetaData *md)
75 mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_MIMETYPE);
78 GNUNET_break (0 == strcmp (mime,
79 GNUNET_FS_DIRECTORY_MIME));
83 GNUNET_CONTAINER_meta_data_insert (md,
85 GNUNET_FS_DIRECTORY_MIME);
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.
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.
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
112 GNUNET_FS_directory_list_contents (size_t size,
115 GNUNET_FS_DirectoryEntryProcessor dep,
118 const char *cdata = data;
124 struct GNUNET_FS_Uri *uri;
125 struct GNUNET_CONTAINER_MetaData *md;
130 (size >= 8 + sizeof (uint32_t)) &&
131 (0 == memcmp (cdata, GNUNET_FS_DIRECTORY_MAGIC, 8)) )
133 memcpy (&mdSize, &cdata[8], sizeof (uint32_t));
134 mdSize = ntohl (mdSize);
135 if (mdSize > size - 8 - sizeof (uint32_t))
138 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
139 _("Not a GNUnet directory.\n"));
142 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[8 +
148 return; /* malformed ! */
156 GNUNET_CONTAINER_meta_data_destroy (md);
157 pos = 8 + sizeof (uint32_t) + mdSize;
161 /* find end of URI */
162 if (cdata[pos] == '\0')
164 /* URI is never empty, must be end of block,
165 skip to next alignment */
167 ((pos / GNUNET_FS_DBLOCK_SIZE) + 1) * GNUNET_FS_DBLOCK_SIZE;
170 /* if we were already aligned, still skip a block! */
171 align += GNUNET_FS_DBLOCK_SIZE;
176 /* malformed - or partial download... */
181 while ((epos < size) && (cdata[epos] != '\0'))
184 return; /* malformed - or partial download */
186 uri = GNUNET_FS_uri_parse (&cdata[pos], &emsg);
191 pos--; /* go back to '\0' to force going to next alignment */
194 if (GNUNET_FS_uri_test_ksk (uri))
196 GNUNET_FS_uri_destroy (uri);
198 return; /* illegal in directory! */
201 memcpy (&mdSize, &cdata[pos], sizeof (uint32_t));
202 mdSize = ntohl (mdSize);
203 pos += sizeof (uint32_t);
204 if (pos + mdSize > size)
206 GNUNET_FS_uri_destroy (uri);
207 return; /* malformed - or partial download */
210 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[pos], mdSize);
213 GNUNET_FS_uri_destroy (uri);
215 return; /* malformed ! */
218 /* FIXME: add support for embedded data */
219 filename = GNUNET_CONTAINER_meta_data_get_by_type (md,
228 GNUNET_free_non_null (filename);
229 GNUNET_CONTAINER_meta_data_destroy (md);
230 GNUNET_FS_uri_destroy (uri);
236 GNUNET_FS_directory_create ()
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.
250 do_align (uint64_t start_position,
251 uint64_t end_position)
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;
263 * Compute a permuation of the blocks to
264 * minimize the cost of alignment. Greedy packer.
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)
272 block_align (uint64_t start,
274 const uint64_t *sizes,
288 for (i = 0; i < count; i++)
291 badness = 0x7FFFFFFF;
293 for (j = i; j < count; j++)
296 cend = cpos + sizes[cval];
297 if (cpos % GNUNET_FS_DBLOCK_SIZE == 0)
299 /* prefer placing the largest blocks first */
300 cbad = -(cend % GNUNET_FS_DBLOCK_SIZE);
304 if (cpos / GNUNET_FS_DBLOCK_SIZE ==
305 cend / GNUNET_FS_DBLOCK_SIZE)
307 /* Data fits into the same block! Prefer small left-overs! */
309 GNUNET_FS_DBLOCK_SIZE - cend % GNUNET_FS_DBLOCK_SIZE;
313 /* Would have to waste space to re-align, add big factor, this
314 case is a real loss (proportional to space wasted)! */
316 GNUNET_FS_DBLOCK_SIZE * (GNUNET_FS_DBLOCK_SIZE -
318 GNUNET_FS_DBLOCK_SIZE);
328 perm[i] = perm[best];
330 cpos += sizes[perm[i]];
331 cpos = do_align (start, cpos);
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>
344 * The first block begins with the directories MAGIC signature,
345 * followed by the meta-data about the directory itself.<p>
347 * After that, the directory consists of block-aligned pairs
348 * of URIs (0-terminated strings) and serialized meta-data.
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
360 GNUNET_FS_directory_create (char **data,
363 const struct GNUNET_FS_Uri **uris,
364 const struct GNUNET_CONTAINER_MetaData **mds,
365 const struct GNUNET_CONTAINER_MetaData *mdir)
377 for (i = 0; i < count; i++)
379 if (GNUNET_FS_uri_test_ksk (fis[i].uri))
382 return GNUNET_SYSERR; /* illegal in directory! */
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++)
393 ucs[i] = GNUNET_FS_uri_to_string (fis[i].uri);
394 GNUNET_assert (ucs[i] != NULL);
396 GNUNET_meta_data_get_serialized_size (fis[i].meta,
397 GNUNET_SERIALIZE_FULL);
404 GNUNET_free (ucs[i--]);
406 return GNUNET_SYSERR;
408 sizes[i] = psize + sizeof (unsigned int) + strlen (ucs[i]) + 1;
410 /* permutate entries to minimize alignment cost */
411 block_align (size, count, sizes, perm);
413 /* compute final size with alignment */
414 for (i = 0; i < count; i++)
417 size += sizes[perm[i]];
418 size = do_align (psize, size);
421 *data = GNUNET_malloc (size);
422 memset (*data, 0, size);
425 memcpy (*data, GNUNET_DIRECTORY_MAGIC, 8);
427 ret = GNUNET_CONTAINER_meta_data_serialize (meta,
429 sizeof (unsigned int)],
430 size - pos - sizeof (unsigned int),
431 GNUNET_SERIALIZE_FULL);
432 GNUNET_assert (ret != GNUNET_SYSERR);
434 memcpy (&(*data)[pos], &ret, sizeof (unsigned int));
435 pos += ntohl (ret) + sizeof (unsigned int);
437 for (j = 0; j < count; j++)
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],
449 sizeof (unsigned int)],
451 sizeof (unsigned int),
452 GNUNET_SERIALIZE_FULL);
453 GNUNET_assert (ret != GNUNET_SYSERR);
455 memcpy (&(*data)[pos], &ret, sizeof (unsigned int));
456 pos += ntohl (ret) + sizeof (unsigned int);
461 GNUNET_assert (pos == size);
468 /* end of fs_directory.c */