2 This file is part of GNUnet.
3 Copyright (C) 2003, 2004, 2006, 2009 GNUnet e.V.
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your 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 Affero General Public License for more details.
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
20 * @file fs/fs_directory.c
21 * @brief Helper functions for building directories.
22 * @author Christian Grothoff
25 * - modify directory builder API to support incremental
26 * generation of directories (to allow directories that
27 * would not fit into memory to be created)
28 * - modify directory processor API to support incremental
29 * iteration over FULL directories (without missing entries)
30 * to allow access to directories that do not fit entirely
34 #include "gnunet_fs_service.h"
38 * String that is used to indicate that a file
39 * is a GNUnet directory.
41 #define GNUNET_DIRECTORY_MAGIC "\211GND\r\n\032\n"
45 * Does the meta-data claim that this is a directory?
46 * Checks if the mime-type is that of a GNUnet directory.
48 * @return #GNUNET_YES if it is, #GNUNET_NO if it is not, #GNUNET_SYSERR if
49 * we have no mime-type information (treat as #GNUNET_NO)
52 GNUNET_FS_meta_data_test_for_directory (const struct GNUNET_CONTAINER_MetaData *md)
59 mime = GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_METATYPE_MIMETYPE);
62 ret = (0 == strcasecmp (mime, GNUNET_FS_DIRECTORY_MIME)) ? GNUNET_YES : GNUNET_NO;
69 * Set the MIMETYPE information for the given
70 * metadata to "application/gnunet-directory".
72 * @param md metadata to add mimetype to
75 GNUNET_FS_meta_data_make_directory (struct GNUNET_CONTAINER_MetaData *md)
80 GNUNET_CONTAINER_meta_data_get_by_type (md, EXTRACTOR_METATYPE_MIMETYPE);
83 GNUNET_break (0 == strcmp (mime, GNUNET_FS_DIRECTORY_MIME));
87 GNUNET_CONTAINER_meta_data_insert (md, "<gnunet>",
88 EXTRACTOR_METATYPE_MIMETYPE,
89 EXTRACTOR_METAFORMAT_UTF8, "text/plain",
90 GNUNET_FS_DIRECTORY_MIME,
91 strlen (GNUNET_FS_DIRECTORY_MIME) + 1);
96 * Closure for 'find_full_data'.
98 struct GetFullDataClosure
102 * Extracted binary meta data.
107 * Number of bytes stored in data.
114 * Type of a function that libextractor calls for each
115 * meta data item found.
117 * @param cls closure (user-defined)
118 * @param plugin_name name of the plugin that produced this value;
119 * special values can be used (i.e. '<zlib>' for zlib being
120 * used in the main libextractor library and yielding
122 * @param type libextractor-type describing the meta data
123 * @param format basic format information about data
124 * @param data_mime_type mime-type of data (not of the original file);
125 * can be NULL (if mime-type is not known)
126 * @param data actual meta-data found
127 * @param data_len number of bytes in data
128 * @return 0 to continue extracting, 1 to abort
131 find_full_data (void *cls, const char *plugin_name,
132 enum EXTRACTOR_MetaType type, enum EXTRACTOR_MetaFormat format,
133 const char *data_mime_type, const char *data, size_t data_len)
135 struct GetFullDataClosure *gfdc = cls;
137 if (type == EXTRACTOR_METATYPE_GNUNET_FULL_DATA)
139 gfdc->size = data_len;
142 gfdc->data = GNUNET_malloc (data_len);
143 GNUNET_memcpy (gfdc->data, data, data_len);
152 * Iterate over all entries in a directory. Note that directories
153 * are structured such that it is possible to iterate over the
154 * individual blocks as well as over the entire directory. Thus
155 * a client can call this function on the buffer in the
156 * GNUNET_FS_ProgressCallback. Also, directories can optionally
157 * include the contents of (small) files embedded in the directory
158 * itself; for those files, the processor may be given the
159 * contents of the file directly by this function.
162 * Note that this function maybe called on parts of directories. Thus
163 * parser errors should not be reported _at all_ (with GNUNET_break).
164 * Still, if some entries can be recovered despite these parsing
165 * errors, the function should try to do this.
167 * @param size number of bytes in data
168 * @param data pointer to the beginning of the directory
169 * @param offset offset of data in the directory
170 * @param dep function to call on each entry
171 * @param dep_cls closure for @a dep
172 * @return #GNUNET_OK if this could be a block in a directory,
173 * #GNUNET_NO if this could be part of a directory (but not 100% OK)
174 * #GNUNET_SYSERR if @a data does not represent a directory
177 GNUNET_FS_directory_list_contents (size_t size,
180 GNUNET_FS_DirectoryEntryProcessor dep,
183 struct GetFullDataClosure full_data;
184 const char *cdata = data;
190 struct GNUNET_FS_Uri *uri;
191 struct GNUNET_CONTAINER_MetaData *md;
195 ((size < 8 + sizeof (uint32_t)) ||
197 GNUNET_FS_DIRECTORY_MAGIC,
199 return GNUNET_SYSERR;
203 GNUNET_memcpy (&mdSize,
206 mdSize = ntohl (mdSize);
207 if (mdSize > size - 8 - sizeof (uint32_t))
210 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
211 _("MAGIC mismatch. This is not a GNUnet directory.\n"));
212 return GNUNET_SYSERR;
214 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[8 + sizeof (uint32_t)],
219 return GNUNET_SYSERR; /* malformed ! */
227 GNUNET_CONTAINER_meta_data_destroy (md);
228 pos = 8 + sizeof (uint32_t) + mdSize;
232 /* find end of URI */
233 if (cdata[pos] == '\0')
235 /* URI is never empty, must be end of block,
236 * skip to next alignment */
237 align = ((pos / DBLOCK_SIZE) + 1) * DBLOCK_SIZE;
240 /* if we were already aligned, still skip a block! */
241 align += DBLOCK_SIZE;
246 /* malformed - or partial download... */
251 while ((epos < size) && (cdata[epos] != '\0'))
254 return GNUNET_NO; /* malformed - or partial download */
256 uri = GNUNET_FS_uri_parse (&cdata[pos], &emsg);
261 pos--; /* go back to '\0' to force going to next alignment */
264 if (GNUNET_FS_uri_test_ksk (uri))
266 GNUNET_FS_uri_destroy (uri);
268 return GNUNET_NO; /* illegal in directory! */
271 GNUNET_memcpy (&mdSize,
274 mdSize = ntohl (mdSize);
275 pos += sizeof (uint32_t);
276 if (pos + mdSize > size)
278 GNUNET_FS_uri_destroy (uri);
279 return GNUNET_NO; /* malformed - or partial download */
282 md = GNUNET_CONTAINER_meta_data_deserialize (&cdata[pos],
286 GNUNET_FS_uri_destroy (uri);
288 return GNUNET_NO; /* malformed ! */
292 GNUNET_CONTAINER_meta_data_get_by_type (md,
293 EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME);
295 full_data.data = NULL;
296 GNUNET_CONTAINER_meta_data_iterate (md,
308 GNUNET_free_non_null (full_data.data);
309 GNUNET_free_non_null (filename);
310 GNUNET_CONTAINER_meta_data_destroy (md);
311 GNUNET_FS_uri_destroy (uri);
317 * Entries in the directory (builder).
322 * This is a linked list.
324 struct BuilderEntry *next;
327 * Length of this entry.
333 * Internal state of a directory builder.
335 struct GNUNET_FS_DirectoryBuilder
338 * Meta-data for the directory itself.
340 struct GNUNET_CONTAINER_MetaData *meta;
343 * Head of linked list of entries.
345 struct BuilderEntry *head;
348 * Number of entires in the directory.
355 * Create a directory builder.
357 * @param mdir metadata for the directory
359 struct GNUNET_FS_DirectoryBuilder *
360 GNUNET_FS_directory_builder_create (const struct GNUNET_CONTAINER_MetaData
363 struct GNUNET_FS_DirectoryBuilder *ret;
365 ret = GNUNET_new (struct GNUNET_FS_DirectoryBuilder);
367 ret->meta = GNUNET_CONTAINER_meta_data_duplicate (mdir);
369 ret->meta = GNUNET_CONTAINER_meta_data_create ();
370 GNUNET_FS_meta_data_make_directory (ret->meta);
376 * Add an entry to a directory.
378 * @param bld directory to extend
379 * @param uri uri of the entry (must not be a KSK)
380 * @param md metadata of the entry
381 * @param data raw data of the entry, can be NULL, otherwise
382 * data must point to exactly the number of bytes specified
383 * by the uri which must be of type LOC or CHK
386 GNUNET_FS_directory_builder_add (struct GNUNET_FS_DirectoryBuilder *bld,
387 const struct GNUNET_FS_Uri *uri,
388 const struct GNUNET_CONTAINER_MetaData *md,
391 struct GNUNET_FS_Uri *curi;
392 struct BuilderEntry *e;
402 struct GNUNET_CONTAINER_MetaData *meta;
403 const struct GNUNET_CONTAINER_MetaData *meta_use;
405 GNUNET_assert (!GNUNET_FS_uri_test_ksk (uri));
408 GNUNET_assert (!GNUNET_FS_uri_test_sks (uri));
409 if (GNUNET_FS_uri_test_chk (uri))
411 fsize = GNUNET_FS_uri_chk_get_file_size (uri);
415 curi = GNUNET_FS_uri_loc_get_uri (uri);
416 GNUNET_assert (NULL != curi);
417 fsize = GNUNET_FS_uri_chk_get_file_size (curi);
418 GNUNET_FS_uri_destroy (curi);
423 fsize = 0; /* not given */
425 if (fsize > MAX_INLINE_SIZE)
426 fsize = 0; /* too large */
427 uris = GNUNET_FS_uri_to_string (uri);
428 slen = strlen (uris) + 1;
429 mds = GNUNET_CONTAINER_meta_data_get_serialized_size (md);
434 meta = GNUNET_CONTAINER_meta_data_duplicate (md);
435 GNUNET_CONTAINER_meta_data_insert (meta, "<gnunet>",
436 EXTRACTOR_METATYPE_GNUNET_FULL_DATA,
437 EXTRACTOR_METAFORMAT_BINARY, NULL, data,
439 mdxs = GNUNET_CONTAINER_meta_data_get_serialized_size (meta);
440 if ((slen + sizeof (uint32_t) + mdxs - 1) / DBLOCK_SIZE ==
441 (slen + sizeof (uint32_t) + mds - 1) / DBLOCK_SIZE)
443 /* adding full data would not cause us to cross
444 * additional blocks, so add it! */
450 if (mds > GNUNET_MAX_MALLOC_CHECKED / 2)
451 mds = GNUNET_MAX_MALLOC_CHECKED / 2;
452 e = GNUNET_malloc (sizeof (struct BuilderEntry) + slen + mds +
454 ser = (char *) &e[1];
455 GNUNET_memcpy (ser, uris, slen);
457 sptr = &ser[slen + sizeof (uint32_t)];
459 GNUNET_CONTAINER_meta_data_serialize (meta_use, &sptr, mds,
460 GNUNET_CONTAINER_META_DATA_SERIALIZE_PART);
462 GNUNET_CONTAINER_meta_data_destroy (meta);
468 GNUNET_memcpy (&ser[slen], &big, sizeof (uint32_t));
469 e->len = slen + sizeof (uint32_t) + mds;
477 * Given the start and end position of a block of
478 * data, return the end position of that data
479 * after alignment to the DBLOCK_SIZE.
482 do_align (size_t start_position, size_t end_position)
486 align = (end_position / DBLOCK_SIZE) * DBLOCK_SIZE;
487 if ((start_position < align) && (end_position > align))
488 return align + end_position - start_position;
494 * Compute a permuation of the blocks to
495 * minimize the cost of alignment. Greedy packer.
497 * @param start starting position for the first block
498 * @param count size of the two arrays
499 * @param sizes the sizes of the individual blocks
500 * @param perm the permutation of the blocks (updated)
503 block_align (size_t start, unsigned int count, const size_t * sizes,
517 for (i = 0; i < count; i++)
520 badness = 0x7FFFFFFF;
522 for (j = i; j < count; j++)
525 cend = cpos + sizes[cval];
526 if (cpos % DBLOCK_SIZE == 0)
528 /* prefer placing the largest blocks first */
529 cbad = -(cend % DBLOCK_SIZE);
533 if (cpos / DBLOCK_SIZE == cend / DBLOCK_SIZE)
535 /* Data fits into the same block! Prefer small left-overs! */
536 cbad = DBLOCK_SIZE - cend % DBLOCK_SIZE;
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 = DBLOCK_SIZE * (DBLOCK_SIZE - cpos % DBLOCK_SIZE);
551 GNUNET_assert (best != -1);
553 perm[i] = perm[best];
555 cpos += sizes[perm[i]];
556 cpos = do_align (start, cpos);
562 * Finish building the directory. Frees the
563 * builder context and returns the directory
566 * @param bld directory to finish
567 * @param rsize set to the number of bytes needed
568 * @param rdata set to the encoded directory
569 * @return #GNUNET_OK on success
572 GNUNET_FS_directory_builder_finish (struct GNUNET_FS_DirectoryBuilder *bld,
582 struct BuilderEntry *pos;
583 struct BuilderEntry **bes;
590 size = strlen (GNUNET_DIRECTORY_MAGIC) + sizeof (uint32_t);
591 size += GNUNET_CONTAINER_meta_data_get_serialized_size (bld->meta);
597 sizes = GNUNET_new_array (bld->count,
599 perm = GNUNET_new_array (bld->count,
601 bes = GNUNET_new_array (bld->count,
602 struct BuilderEntry *);
604 for (i = 0; i < bld->count; i++)
611 block_align (size, bld->count, sizes, perm);
612 /* compute final size with alignment */
613 for (i = 0; i < bld->count; i++)
616 size += sizes[perm[i]];
617 size = do_align (psize, size);
621 data = GNUNET_malloc_large (size);
624 GNUNET_log_strerror (GNUNET_ERROR_TYPE_ERROR,
628 GNUNET_free_non_null (sizes);
629 GNUNET_free_non_null (perm);
630 GNUNET_free_non_null (bes);
631 return GNUNET_SYSERR;
635 GNUNET_DIRECTORY_MAGIC,
636 strlen (GNUNET_DIRECTORY_MAGIC));
637 off = strlen (GNUNET_DIRECTORY_MAGIC);
639 sptr = &data[off + sizeof (uint32_t)];
641 GNUNET_CONTAINER_meta_data_serialize (bld->meta,
643 size - off - sizeof (uint32_t),
644 GNUNET_CONTAINER_META_DATA_SERIALIZE_FULL);
645 GNUNET_assert (ret != -1);
647 GNUNET_memcpy (&data[off],
650 off += sizeof (uint32_t) + ret;
651 for (j = 0; j < bld->count; j++)
656 off = do_align (psize, off);
657 GNUNET_memcpy (&data[off - sizes[i]], &(bes[i])[1], sizes[i]);
658 GNUNET_free (bes[i]);
660 GNUNET_free_non_null (sizes);
661 GNUNET_free_non_null (perm);
662 GNUNET_free_non_null (bes);
663 GNUNET_assert (off == size);
664 GNUNET_CONTAINER_meta_data_destroy (bld->meta);
670 /* end of fs_directory.c */