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 3, 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"
40 * String that is used to indicate that a file
41 * is a GNUnet directory.
43 #define GNUNET_DIRECTORY_MAGIC "\211GND\r\n\032\n"
47 * Does the meta-data claim that this is a directory?
48 * Checks if the mime-type is that of a GNUnet directory.
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')
54 GNUNET_FS_meta_data_test_for_directory (const struct GNUNET_CONTAINER_MetaData
63 GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_METATYPE_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)
84 GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_METATYPE_MIMETYPE);
87 GNUNET_break (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME));
91 GNUNET_CONTAINER_meta_data_insert (md, "<gnunet>",
92 EXTRACTOR_METATYPE_MIMETYPE,
93 EXTRACTOR_METAFORMAT_UTF8, "text/plain",
94 GNUNET_FS_DIRECTORY_MIME,
95 strlen (GNUNET_FS_DIRECTORY_MIME) + 1);
100 * Closure for 'find_full_data'.
102 struct GetFullDataClosure
106 * Extracted binary meta data.
111 * Number of bytes stored in data.
118 * Type of a function that libextractor calls for each
119 * meta data item found.
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. '<zlib>' for zlib being
124 * used in the main libextractor library and yielding
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
135 find_full_data (void *cls, const char *plugin_name,
136 enum EXTRACTOR_MetaType type, enum EXTRACTOR_MetaFormat format,
137 const char *data_mime_type, const char *data, size_t data_len)
139 struct GetFullDataClosure *gfdc = cls;
141 if (type == EXTRACTOR_METATYPE_GNUNET_FULL_DATA)
143 gfdc->size = data_len;
146 gfdc->data = GNUNET_malloc (data_len);
147 memcpy (gfdc->data, data, data_len);
156 * Iterate over all entries in a directory. Note that directories
157 * are structured such that it is possible to iterate over the
158 * individual blocks as well as over the entire directory. Thus
159 * a client can call this function on the buffer in the
160 * GNUNET_FS_ProgressCallback. Also, directories can optionally
161 * include the contents of (small) files embedded in the directory
162 * itself; for those files, the processor may be given the
163 * contents of the file directly by this function.
166 * Note that this function maybe called on parts of directories. Thus
167 * parser errors should not be reported _at all_ (with GNUNET_break).
168 * Still, if some entries can be recovered despite these parsing
169 * errors, the function should try to do this.
171 * @param size number of bytes in data
172 * @param data pointer to the beginning of the directory
173 * @param offset offset of data in the directory
174 * @param dep function to call on each entry
175 * @param dep_cls closure for dep
176 * @return GNUNET_OK if this could be a block in a directory,
177 * GNUNET_NO if this could be part of a directory (but not 100% OK)
178 * GNUNET_SYSERR if 'data' does not represent a directory
181 GNUNET_FS_directory_list_contents (size_t size, const void *data,
183 GNUNET_FS_DirectoryEntryProcessor dep,
186 struct GetFullDataClosure full_data;
187 const char *cdata = data;
193 struct GNUNET_FS_Uri *uri;
194 struct GNUNET_CONTAINER_MetaData *md;
198 ((size < 8 + sizeof (uint32_t)) ||
199 (0 != memcmp (cdata, GNUNET_FS_DIRECTORY_MAGIC, 8))))
201 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
202 _("MAGIC mismatch. This is not a GNUnet directory.\n"));
203 return GNUNET_SYSERR;
208 memcpy (&mdSize, &cdata[8], sizeof (uint32_t));
209 mdSize = ntohl (mdSize);
210 if (mdSize > size - 8 - sizeof (uint32_t))
213 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
214 _("MAGIC mismatch. This is not a GNUnet directory.\n"));
215 return GNUNET_SYSERR;
217 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[8 + sizeof (uint32_t)],
222 return GNUNET_SYSERR; /* malformed ! */
224 dep (dep_cls, NULL, NULL, md, 0, NULL);
225 GNUNET_CONTAINER_meta_data_destroy (md);
226 pos = 8 + sizeof (uint32_t) + mdSize;
230 /* find end of URI */
231 if (cdata[pos] == '\0')
233 /* URI is never empty, must be end of block,
234 * skip to next alignment */
235 align = ((pos / DBLOCK_SIZE) + 1) * DBLOCK_SIZE;
238 /* if we were already aligned, still skip a block! */
239 align += DBLOCK_SIZE;
244 /* malformed - or partial download... */
249 while ((epos < size) && (cdata[epos] != '\0'))
252 return GNUNET_NO; /* malformed - or partial download */
254 uri = GNUNET_FS_uri_parse (&cdata[pos], &emsg);
259 pos--; /* go back to '\0' to force going to next alignment */
262 if (GNUNET_FS_uri_test_ksk (uri))
264 GNUNET_FS_uri_destroy (uri);
266 return GNUNET_NO; /* illegal in directory! */
269 memcpy (&mdSize, &cdata[pos], sizeof (uint32_t));
270 mdSize = ntohl (mdSize);
271 pos += sizeof (uint32_t);
272 if (pos + mdSize > size)
274 GNUNET_FS_uri_destroy (uri);
275 return GNUNET_NO; /* malformed - or partial download */
278 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[pos], mdSize);
281 GNUNET_FS_uri_destroy (uri);
283 return GNUNET_NO; /* malformed ! */
287 GNUNET_CONTAINER_meta_data_get_by_type (md,
288 EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME);
290 full_data.data = NULL;
291 GNUNET_CONTAINER_meta_data_iterate (md, &find_full_data, &full_data);
294 dep (dep_cls, filename, uri, md, full_data.size, full_data.data);
296 GNUNET_free_non_null (full_data.data);
297 GNUNET_free_non_null (filename);
298 GNUNET_CONTAINER_meta_data_destroy (md);
299 GNUNET_FS_uri_destroy (uri);
305 * Entries in the directory (builder).
310 * This is a linked list.
312 struct BuilderEntry *next;
315 * Length of this entry.
321 * Internal state of a directory builder.
323 struct GNUNET_FS_DirectoryBuilder
326 * Meta-data for the directory itself.
328 struct GNUNET_CONTAINER_MetaData *meta;
331 * Head of linked list of entries.
333 struct BuilderEntry *head;
336 * Number of entires in the directory.
343 * Create a directory builder.
345 * @param mdir metadata for the directory
347 struct GNUNET_FS_DirectoryBuilder *
348 GNUNET_FS_directory_builder_create (const struct GNUNET_CONTAINER_MetaData
351 struct GNUNET_FS_DirectoryBuilder *ret;
353 ret = GNUNET_malloc (sizeof (struct GNUNET_FS_DirectoryBuilder));
355 ret->meta = GNUNET_CONTAINER_meta_data_duplicate (mdir);
357 ret->meta = GNUNET_CONTAINER_meta_data_create ();
358 GNUNET_FS_meta_data_make_directory (ret->meta);
364 * Add an entry to a directory.
366 * @param bld directory to extend
367 * @param uri uri of the entry (must not be a KSK)
368 * @param md metadata of the entry
369 * @param data raw data of the entry, can be NULL, otherwise
370 * data must point to exactly the number of bytes specified
371 * by the uri which must be of type LOC or CHK
374 GNUNET_FS_directory_builder_add (struct GNUNET_FS_DirectoryBuilder *bld,
375 const struct GNUNET_FS_Uri *uri,
376 const struct GNUNET_CONTAINER_MetaData *md,
379 struct GNUNET_FS_Uri *curi;
380 struct BuilderEntry *e;
390 struct GNUNET_CONTAINER_MetaData *meta;
391 const struct GNUNET_CONTAINER_MetaData *meta_use;
393 GNUNET_assert (!GNUNET_FS_uri_test_ksk (uri));
396 GNUNET_assert (!GNUNET_FS_uri_test_sks (uri));
397 if (GNUNET_FS_uri_test_chk (uri))
399 fsize = GNUNET_FS_uri_chk_get_file_size (uri);
403 curi = GNUNET_FS_uri_loc_get_uri (uri);
404 GNUNET_assert (NULL != curi);
405 fsize = GNUNET_FS_uri_chk_get_file_size (curi);
406 GNUNET_FS_uri_destroy (curi);
411 fsize = 0; /* not given */
413 if (fsize > MAX_INLINE_SIZE)
414 fsize = 0; /* too large */
415 uris = GNUNET_FS_uri_to_string (uri);
416 slen = strlen (uris) + 1;
417 mds = GNUNET_CONTAINER_meta_data_get_serialized_size (md);
422 meta = GNUNET_CONTAINER_meta_data_duplicate (md);
423 GNUNET_CONTAINER_meta_data_insert (meta, "<gnunet>",
424 EXTRACTOR_METATYPE_GNUNET_FULL_DATA,
425 EXTRACTOR_METAFORMAT_BINARY, NULL, data,
427 mdxs = GNUNET_CONTAINER_meta_data_get_serialized_size (meta);
428 if ((slen + sizeof (uint32_t) + mdxs - 1) / DBLOCK_SIZE ==
429 (slen + sizeof (uint32_t) + mds - 1) / DBLOCK_SIZE)
431 /* adding full data would not cause us to cross
432 * additional blocks, so add it! */
438 if (mds > GNUNET_MAX_MALLOC_CHECKED / 2)
439 mds = GNUNET_MAX_MALLOC_CHECKED / 2;
440 e = GNUNET_malloc (sizeof (struct BuilderEntry) + slen + mds +
442 ser = (char *) &e[1];
443 memcpy (ser, uris, slen);
445 sptr = &ser[slen + sizeof (uint32_t)];
447 GNUNET_CONTAINER_meta_data_serialize (meta_use, &sptr, mds,
448 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
450 GNUNET_CONTAINER_meta_data_destroy (meta);
456 memcpy (&ser[slen], &big, sizeof (uint32_t));
457 e->len = slen + sizeof (uint32_t) + mds;
465 * Given the start and end position of a block of
466 * data, return the end position of that data
467 * after alignment to the DBLOCK_SIZE.
470 do_align (size_t start_position, size_t end_position)
474 align = (end_position / DBLOCK_SIZE) * DBLOCK_SIZE;
475 if ((start_position < align) && (end_position > align))
476 return align + end_position - start_position;
482 * Compute a permuation of the blocks to
483 * minimize the cost of alignment. Greedy packer.
485 * @param start starting position for the first block
486 * @param count size of the two arrays
487 * @param sizes the sizes of the individual blocks
488 * @param perm the permutation of the blocks (updated)
491 block_align (size_t start, unsigned int count, const size_t * sizes,
505 for (i = 0; i < count; i++)
508 badness = 0x7FFFFFFF;
510 for (j = i; j < count; j++)
513 cend = cpos + sizes[cval];
514 if (cpos % DBLOCK_SIZE == 0)
516 /* prefer placing the largest blocks first */
517 cbad = -(cend % DBLOCK_SIZE);
521 if (cpos / DBLOCK_SIZE == cend / DBLOCK_SIZE)
523 /* Data fits into the same block! Prefer small left-overs! */
524 cbad = DBLOCK_SIZE - cend % DBLOCK_SIZE;
528 /* Would have to waste space to re-align, add big factor, this
529 * case is a real loss (proportional to space wasted)! */
530 cbad = DBLOCK_SIZE * (DBLOCK_SIZE - cpos % DBLOCK_SIZE);
539 GNUNET_assert (best != -1);
541 perm[i] = perm[best];
543 cpos += sizes[perm[i]];
544 cpos = do_align (start, cpos);
550 * Finish building the directory. Frees the
551 * builder context and returns the directory
554 * @param bld directory to finish
555 * @param rsize set to the number of bytes needed
556 * @param rdata set to the encoded directory
557 * @return GNUNET_OK on success
560 GNUNET_FS_directory_builder_finish (struct GNUNET_FS_DirectoryBuilder *bld,
561 size_t * rsize, void **rdata)
569 struct BuilderEntry *pos;
570 struct BuilderEntry **bes;
577 size = strlen (GNUNET_DIRECTORY_MAGIC) + sizeof (uint32_t);
578 size += GNUNET_CONTAINER_meta_data_get_serialized_size (bld->meta);
584 sizes = GNUNET_malloc (bld->count * sizeof (size_t));
585 perm = GNUNET_malloc (bld->count * sizeof (unsigned int));
586 bes = GNUNET_malloc (bld->count * sizeof (struct BuilderEntry *));
588 for (i = 0; i < bld->count; i++)
595 block_align (size, bld->count, sizes, perm);
596 /* compute final size with alignment */
597 for (i = 0; i < bld->count; i++)
600 size += sizes[perm[i]];
601 size = do_align (psize, size);
605 data = GNUNET_malloc_large (size);
608 GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR, "malloc");
611 GNUNET_free_non_null (sizes);
612 GNUNET_free_non_null (perm);
613 GNUNET_free_non_null (bes);
614 return GNUNET_SYSERR;
617 memcpy (data, GNUNET_DIRECTORY_MAGIC, strlen (GNUNET_DIRECTORY_MAGIC));
618 off = strlen (GNUNET_DIRECTORY_MAGIC);
620 sptr = &data[off + sizeof (uint32_t)];
622 GNUNET_CONTAINER_meta_data_serialize (bld->meta, &sptr,
623 size - off - sizeof (uint32_t),
624 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
625 GNUNET_assert (ret != -1);
627 memcpy (&data[off], &big, sizeof (uint32_t));
628 off += sizeof (uint32_t) + ret;
629 for (j = 0; j < bld->count; j++)
634 off = do_align (psize, off);
635 memcpy (&data[off - sizes[i]], &(bes[i])[1], sizes[i]);
636 GNUNET_free (bes[i]);
638 GNUNET_free_non_null (sizes);
639 GNUNET_free_non_null (perm);
640 GNUNET_free_non_null (bes);
641 GNUNET_assert (off == size);
642 GNUNET_CONTAINER_meta_data_destroy (bld->meta);
648 /* end of fs_directory.c */