fs_sharetree.c

Go to the documentation of this file.

/*
     This file is part of GNUnet
     Copyright (C) 2005-2012 GNUnet e.V.
 
     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     or (at your option) any later version.
 
     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Affero General Public License for more details.
 
     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
     SPDX-License-Identifier: AGPL3.0-or-later
 */
 
#include "platform.h"
 
#include "gnunet_fs_service.h"
#include "gnunet_scheduler_lib.h"
#include <pthread.h>
 
 
struct KeywordCounter
{
  struct KeywordCounter *prev;
 
  struct KeywordCounter *next;
 
  const char *value;
 
  unsigned int count;
};
 
 
struct MetaCounter
{
  struct MetaCounter *prev;
 
  struct MetaCounter *next;
 
  const char *plugin_name;
 
  const char *data_mime_type;
 
  const char *data;
 
  size_t data_size;
 
  enum EXTRACTOR_MetaType type;
 
  enum EXTRACTOR_MetaFormat format;
 
  unsigned int count;
};
 
 
struct TrimContext
{
  struct GNUNET_CONTAINER_MultiHashMap *keywordcounter;
 
  struct GNUNET_CONTAINER_MultiHashMap *metacounter;
 
  struct GNUNET_FS_ShareTreeItem *pos;
 
  unsigned int move_threshold;
};
 
 
static int
add_to_keyword_counter (void *cls, const char *keyword, int is_mandatory)
{
  struct GNUNET_CONTAINER_MultiHashMap *mcm = cls;
  struct KeywordCounter *cnt;
  struct GNUNET_HashCode hc;
  size_t klen;
 
  klen = strlen (keyword) + 1;
  GNUNET_CRYPTO_hash (keyword, klen - 1, &hc);
  cnt = GNUNET_CONTAINER_multihashmap_get (mcm, &hc);
  if (cnt == NULL)
  {
    cnt = GNUNET_malloc (sizeof(struct KeywordCounter) + klen);
    cnt->value = (const char *) &cnt[1];
    GNUNET_memcpy (&cnt[1], keyword, klen);
    GNUNET_assert (GNUNET_OK ==
                   GNUNET_CONTAINER_multihashmap_put (mcm,
                                                      &hc, cnt,
                                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
  }
  cnt->count++;
  return GNUNET_OK;
}
 
 
static int
add_to_meta_counter (void *cls, const char *plugin_name,
                     enum EXTRACTOR_MetaType type, enum EXTRACTOR_MetaFormat
                     format,
                     const char *data_mime_type, const char *data, size_t
                     data_len)
{
  struct GNUNET_CONTAINER_MultiHashMap *map = cls;
  struct GNUNET_HashCode key;
  struct MetaCounter *cnt;
 
  GNUNET_CRYPTO_hash (data, data_len, &key);
  cnt = GNUNET_CONTAINER_multihashmap_get (map, &key);
  if (NULL == cnt)
  {
    cnt = GNUNET_new (struct MetaCounter);
    cnt->data = data;
    cnt->data_size = data_len;
    cnt->plugin_name = plugin_name;
    cnt->type = type;
    cnt->format = format;
    cnt->data_mime_type = data_mime_type;
    GNUNET_assert (GNUNET_OK ==
                   GNUNET_CONTAINER_multihashmap_put (map,
                                                      &key, cnt,
                                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
  }
  cnt->count++;
  return 0;
}
 
 
static int
remove_high_frequency_keywords (void *cls, const char *keyword, int
                                is_mandatory)
{
  struct TrimContext *tc = cls;
  struct KeywordCounter *counter;
  struct GNUNET_HashCode hc;
  size_t klen;
 
  klen = strlen (keyword) + 1;
  GNUNET_CRYPTO_hash (keyword, klen - 1, &hc);
  counter = GNUNET_CONTAINER_multihashmap_get (tc->keywordcounter, &hc);
  GNUNET_assert (NULL != counter);
  if (counter->count < tc->move_threshold)
    return GNUNET_OK;
  GNUNET_FS_uri_ksk_remove_keyword (tc->pos->ksk_uri,
                                    counter->value);
  return GNUNET_OK;
}
 
 
static int
migrate_and_drop_keywords (void *cls, const struct GNUNET_HashCode *key,
                           void *value)
{
  struct TrimContext *tc = cls;
  struct KeywordCounter *counter = value;
 
  if (counter->count >= tc->move_threshold)
  {
    if (NULL == tc->pos->ksk_uri)
      tc->pos->ksk_uri = GNUNET_FS_uri_ksk_create_from_args (1,
                                                             &counter->value);
    else
      GNUNET_FS_uri_ksk_add_keyword (tc->pos->ksk_uri, counter->value,
                                     GNUNET_NO);
  }
  GNUNET_assert (GNUNET_YES ==
                 GNUNET_CONTAINER_multihashmap_remove (tc->keywordcounter,
                                                       key,
                                                       counter));
  GNUNET_free (counter);
  return GNUNET_YES;
}
 
 
static int
migrate_and_drop_metadata (void *cls, const struct GNUNET_HashCode *key,
                           void *value)
{
  struct TrimContext *tc = cls;
  struct MetaCounter *counter = value;
 
  if (counter->count >= tc->move_threshold)
  {
    if (NULL == tc->pos->meta)
      tc->pos->meta = GNUNET_FS_meta_data_create ();
    GNUNET_FS_meta_data_insert (tc->pos->meta,
                                counter->plugin_name,
                                counter->type,
                                counter->format,
                                counter->data_mime_type, counter->data,
                                counter->data_size);
  }
  GNUNET_assert (GNUNET_YES ==
                 GNUNET_CONTAINER_multihashmap_remove (tc->metacounter,
                                                       key,
                                                       counter));
  GNUNET_free (counter);
  return GNUNET_YES;
}
 
 
static void
share_tree_trim (struct TrimContext *tc,
                 struct GNUNET_FS_ShareTreeItem *tree)
{
  struct GNUNET_FS_ShareTreeItem *pos;
  unsigned int num_children;
 
  /* first, trim all children */
  num_children = 0;
  for (pos = tree->children_head; NULL != pos; pos = pos->next)
  {
    share_tree_trim (tc, pos);
    num_children++;
  }
 
  /* consider adding filename to directory meta data */
  if (tree->is_directory == GNUNET_YES)
  {
    const char *user = getenv ("USER");
    if ((user == NULL) ||
        (0 != strncasecmp (user, tree->short_filename, strlen (user))))
    {
      /* only use filename if it doesn't match $USER */
      if (NULL == tree->meta)
        tree->meta = GNUNET_FS_meta_data_create ();
      GNUNET_FS_meta_data_insert (tree->meta, "<libgnunetfs>",
                                  EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME,
                                  EXTRACTOR_METAFORMAT_UTF8,
                                  "text/plain", tree->short_filename,
                                  strlen (tree->short_filename) + 1);
    }
  }
 
  if (1 >= num_children)
    return; /* nothing to trim */
 
  /* now, count keywords and meta data in children */
  for (pos = tree->children_head; NULL != pos; pos = pos->next)
  {
    if (NULL != pos->meta)
      GNUNET_FS_meta_data_iterate (pos->meta, &add_to_meta_counter,
                                   tc->metacounter);
    if (NULL != pos->ksk_uri)
      GNUNET_FS_uri_ksk_get_keywords (pos->ksk_uri, &add_to_keyword_counter,
                                      tc->keywordcounter);
  }
 
  /* calculate threshold for moving keywords / meta data */
  tc->move_threshold = 1 + (num_children / 2);
 
  /* remove high-frequency keywords from children */
  for (pos = tree->children_head; NULL != pos; pos = pos->next)
  {
    tc->pos = pos;
    if (NULL != pos->ksk_uri)
    {
      struct GNUNET_FS_Uri *ksk_uri_copy = GNUNET_FS_uri_dup (pos->ksk_uri);
      GNUNET_FS_uri_ksk_get_keywords (ksk_uri_copy,
                                      &remove_high_frequency_keywords, tc);
      GNUNET_FS_uri_destroy (ksk_uri_copy);
    }
  }
 
  /* add high-frequency meta data and keywords to parent */
  tc->pos = tree;
  GNUNET_CONTAINER_multihashmap_iterate (tc->keywordcounter,
                                         &migrate_and_drop_keywords,
                                         tc);
  GNUNET_CONTAINER_multihashmap_iterate (tc->metacounter,
                                         &migrate_and_drop_metadata,
                                         tc);
}
 
 
void
GNUNET_FS_share_tree_trim (struct GNUNET_FS_ShareTreeItem *toplevel)
{
  struct TrimContext tc;
 
  if (toplevel == NULL)
    return;
  tc.keywordcounter = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_NO);
  tc.metacounter = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_NO);
  share_tree_trim (&tc, toplevel);
  GNUNET_CONTAINER_multihashmap_destroy (tc.keywordcounter);
  GNUNET_CONTAINER_multihashmap_destroy (tc.metacounter);
}
 
 
void
GNUNET_FS_share_tree_free (struct GNUNET_FS_ShareTreeItem *toplevel)
{
  struct GNUNET_FS_ShareTreeItem *pos;
 
  while (NULL != (pos = toplevel->children_head))
    GNUNET_FS_share_tree_free (pos);
  if (NULL != toplevel->parent)
    GNUNET_CONTAINER_DLL_remove (toplevel->parent->children_head,
                                 toplevel->parent->children_tail,
                                 toplevel);
  if (NULL != toplevel->meta)
    GNUNET_FS_meta_data_destroy (toplevel->meta);
  if (NULL != toplevel->ksk_uri)
    GNUNET_FS_uri_destroy (toplevel->ksk_uri);
  GNUNET_free (toplevel->filename);
  GNUNET_free (toplevel->short_filename);
  GNUNET_free (toplevel);
}
 
 
/* end fs_sharetree.c */