src/fs/fs_sharetree.c

   1 /*
   2      This file is part of GNUnet
   3      Copyright (C) 2005-2012 GNUnet e.V.
   4
   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.
   9
  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.
  14
  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/>.
  17 */
  18
  19 /**
  20  * @file fs/fs_sharetree.c
  21  * @brief code to manipulate the 'struct GNUNET_FS_ShareTreeItem' tree
  22  * @author LRN
  23  * @author Christian Grothoff
  24  */
  25 #include "platform.h"
  26 #include "gnunet_fs_service.h"
  27 #include "gnunet_scheduler_lib.h"
  28 #include <pthread.h>
  29
  30
  31 /**
  32  * Entry for each unique keyword to track how often
  33  * it occured.  Contains the keyword and the counter.
  34  */
  35 struct KeywordCounter
  36 {
  37
  38   /**
  39    * This is a doubly-linked list
  40    */
  41   struct KeywordCounter *prev;
  42
  43   /**
  44    * This is a doubly-linked list
  45    */
  46   struct KeywordCounter *next;
  47
  48   /**
  49    * Keyword that was found.
  50    */
  51   const char *value;
  52
  53   /**
  54    * How many files have this keyword?
  55    */
  56   unsigned int count;
  57
  58 };
  59
  60
  61 /**
  62  * Aggregate information we keep for meta data in each directory.
  63  */
  64 struct MetaCounter
  65 {
  66
  67   /**
  68    * This is a doubly-linked list
  69    */
  70   struct MetaCounter *prev;
  71
  72   /**
  73    * This is a doubly-linked list
  74    */
  75   struct MetaCounter *next;
  76
  77   /**
  78    * Name of the plugin that provided that piece of metadata
  79    */
  80   const char *plugin_name;
  81
  82   /**
  83    * MIME-type of the metadata itself
  84    */
  85   const char *data_mime_type;
  86
  87   /**
  88    * The actual meta data.
  89    */
  90   const char *data;
  91
  92   /**
  93    * Number of bytes in 'data'.
  94    */
  95   size_t data_size;
  96
  97   /**
  98    * Type of the data
  99    */
 100   enum EXTRACTOR_MetaType type;
 101
 102   /**
 103    * Format of the data
 104    */
 105   enum EXTRACTOR_MetaFormat format;
 106
 107   /**
 108    * How many files have meta entries matching this value?
 109    * (type and format do not have to match).
 110    */
 111   unsigned int count;
 112
 113 };
 114
 115
 116 /**
 117  * A structure that forms a singly-linked list that serves as a stack
 118  * for metadata-processing function.
 119  */
 120 struct TrimContext
 121 {
 122
 123   /**
 124    * Map from the hash over the keyword to an 'struct KeywordCounter *'
 125    * counter that says how often this keyword was
 126    * encountered in the current directory.
 127    */
 128   struct GNUNET_CONTAINER_MultiHashMap *keywordcounter;
 129
 130   /**
 131    * Map from the hash over the metadata to an 'struct MetaCounter *'
 132    * counter that says how often this metadata was
 133    * encountered in the current directory.
 134    */
 135   struct GNUNET_CONTAINER_MultiHashMap *metacounter;
 136
 137   /**
 138    * Position we are currently manipulating.
 139    */
 140   struct GNUNET_FS_ShareTreeItem *pos;
 141
 142   /**
 143    * Number of times an item has to be found to be moved to the parent.
 144    */
 145   unsigned int move_threshold;
 146
 147 };
 148
 149
 150 /**
 151  * Add the given keyword to the keyword statistics tracker.
 152  *
 153  * @param cls the multihashmap we store the keyword counters in
 154  * @param keyword the keyword to count
 155  * @param is_mandatory ignored
 156  * @return always GNUNET_OK
 157  */
 158 static int
 159 add_to_keyword_counter (void *cls, const char *keyword, int is_mandatory)
 160 {
 161   struct GNUNET_CONTAINER_MultiHashMap *mcm = cls;
 162   struct KeywordCounter *cnt;
 163   struct GNUNET_HashCode hc;
 164   size_t klen;
 165
 166   klen = strlen (keyword) + 1;
 167   GNUNET_CRYPTO_hash (keyword, klen - 1, &hc);
 168   cnt = GNUNET_CONTAINER_multihashmap_get (mcm, &hc);
 169   if (cnt == NULL)
 170   {
 171     cnt = GNUNET_malloc (sizeof (struct KeywordCounter) + klen);
 172     cnt->value = (const char *) &cnt[1];
 173     GNUNET_memcpy (&cnt[1], keyword, klen);
 174     GNUNET_assert (GNUNET_OK ==
 175                    GNUNET_CONTAINER_multihashmap_put (mcm,
 176                                                       &hc, cnt,
 177                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 178   }
 179   cnt->count++;
 180   return GNUNET_OK;
 181 }
 182
 183
 184 /**
 185  * Function called on each meta data item.  Increments the
 186  * respective counter.
 187  *
 188  * @param cls the container multihashmap to update
 189  * @param plugin_name name of the plugin that produced this value;
 190  *        special values can be used (i.e. '&lt;zlib&gt;' for zlib being
 191  *        used in the main libextractor library and yielding
 192  *        meta data).
 193  * @param type libextractor-type describing the meta data
 194  * @param format basic format information about data
 195  * @param data_mime_type mime-type of data (not of the original file);
 196  *        can be NULL (if mime-type is not known)
 197  * @param data actual meta-data found
 198  * @param data_len number of bytes in data
 199  * @return 0 to continue extracting / iterating
 200  */
 201 static int
 202 add_to_meta_counter (void *cls, const char *plugin_name,
 203                      enum EXTRACTOR_MetaType type, enum EXTRACTOR_MetaFormat format,
 204                      const char *data_mime_type, const char *data, size_t data_len)
 205 {
 206   struct GNUNET_CONTAINER_MultiHashMap *map = cls;
 207   struct GNUNET_HashCode key;
 208   struct MetaCounter *cnt;
 209
 210   GNUNET_CRYPTO_hash (data, data_len, &key);
 211   cnt = GNUNET_CONTAINER_multihashmap_get (map, &key);
 212   if (NULL == cnt)
 213   {
 214     cnt = GNUNET_new (struct MetaCounter);
 215     cnt->data = data;
 216     cnt->data_size = data_len;
 217     cnt->plugin_name = plugin_name;
 218     cnt->type = type;
 219     cnt->format = format;
 220     cnt->data_mime_type = data_mime_type;
 221     GNUNET_assert (GNUNET_OK ==
 222                    GNUNET_CONTAINER_multihashmap_put (map,
 223                                                       &key, cnt,
 224                                                       GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 225   }
 226   cnt->count++;
 227   return 0;
 228 }
 229
 230
 231 /**
 232  * Remove keywords above the threshold.
 233  *
 234  * @param cls the 'struct TrimContext' with the pos to remove the keywords from
 235  * @param keyword the keyword to check
 236  * @param is_mandatory ignored
 237  * @return always GNUNET_OK
 238  */
 239 static int
 240 remove_high_frequency_keywords (void *cls, const char *keyword, int is_mandatory)
 241 {
 242   struct TrimContext *tc = cls;
 243   struct KeywordCounter *counter;
 244   struct GNUNET_HashCode hc;
 245   size_t klen;
 246
 247   klen = strlen (keyword) + 1;
 248   GNUNET_CRYPTO_hash (keyword, klen - 1, &hc);
 249   counter = GNUNET_CONTAINER_multihashmap_get (tc->keywordcounter, &hc);
 250   GNUNET_assert (NULL != counter);
 251   if (counter->count < tc->move_threshold)
 252     return GNUNET_OK;
 253   GNUNET_FS_uri_ksk_remove_keyword (tc->pos->ksk_uri,
 254                                     counter->value);
 255   return GNUNET_OK;
 256 }
 257
 258
 259 /**
 260  * Move "frequent" keywords over to the target ksk uri, free the
 261  * counters.
 262  *
 263  * @param cls the 'struct TrimContext'
 264  * @param key key of the entry
 265  * @param value the 'struct KeywordCounter'
 266  * @return GNUNET_YES (always)
 267  */
 268 static int
 269 migrate_and_drop_keywords (void *cls, const struct GNUNET_HashCode * key, void *value)
 270 {
 271   struct TrimContext *tc = cls;
 272   struct KeywordCounter *counter = value;
 273
 274   if (counter->count >= tc->move_threshold)
 275   {
 276     if (NULL == tc->pos->ksk_uri)
 277       tc->pos->ksk_uri = GNUNET_FS_uri_ksk_create_from_args (1, &counter->value);
 278     else
 279       GNUNET_FS_uri_ksk_add_keyword (tc->pos->ksk_uri, counter->value, GNUNET_NO);
 280   }
 281   GNUNET_assert (GNUNET_YES ==
 282                  GNUNET_CONTAINER_multihashmap_remove (tc->keywordcounter,
 283                                                        key,
 284                                                        counter));
 285   GNUNET_free (counter);
 286   return GNUNET_YES;
 287 }
 288
 289
 290 /**
 291  * Copy "frequent" metadata items over to the
 292  * target metadata container, free the counters.
 293  *
 294  * @param cls the 'struct TrimContext'
 295  * @param key key of the entry
 296  * @param value the 'struct KeywordCounter'
 297  * @return GNUNET_YES (always)
 298  */
 299 static int
 300 migrate_and_drop_metadata (void *cls, const struct GNUNET_HashCode * key, void *value)
 301 {
 302   struct TrimContext *tc = cls;
 303   struct MetaCounter *counter = value;
 304
 305   if (counter->count >= tc->move_threshold)
 306   {
 307     if (NULL == tc->pos->meta)
 308       tc->pos->meta = GNUNET_CONTAINER_meta_data_create ();
 309     GNUNET_CONTAINER_meta_data_insert (tc->pos->meta,
 310                                        counter->plugin_name,
 311                                        counter->type,
 312                                        counter->format,
 313                                        counter->data_mime_type, counter->data,
 314                                        counter->data_size);
 315   }
 316   GNUNET_assert (GNUNET_YES ==
 317                  GNUNET_CONTAINER_multihashmap_remove (tc->metacounter,
 318                                                        key,
 319                                                        counter));
 320   GNUNET_free (counter);
 321   return GNUNET_YES;
 322 }
 323
 324
 325 /**
 326  * Process a share item tree, moving frequent keywords up and
 327  * copying frequent metadata up.
 328  *
 329  * @param tc trim context with hash maps to use
 330  * @param tree tree to trim
 331  */
 332 static void
 333 share_tree_trim (struct TrimContext *tc,
 334                  struct GNUNET_FS_ShareTreeItem *tree)
 335 {
 336   struct GNUNET_FS_ShareTreeItem *pos;
 337   unsigned int num_children;
 338
 339   /* first, trim all children */
 340   num_children = 0;
 341   for (pos = tree->children_head; NULL != pos; pos = pos->next)
 342   {
 343     share_tree_trim (tc, pos);
 344     num_children++;
 345   }
 346
 347   /* consider adding filename to directory meta data */
 348   if (tree->is_directory == GNUNET_YES)
 349   {
 350     const char *user = getenv ("USER");
 351     if ( (user == NULL) ||
 352          (0 != strncasecmp (user, tree->short_filename, strlen(user))))
 353     {
 354       /* only use filename if it doesn't match $USER */
 355       if (NULL == tree->meta)
 356         tree->meta = GNUNET_CONTAINER_meta_data_create ();
 357       GNUNET_CONTAINER_meta_data_insert (tree->meta, "<libgnunetfs>",
 358                                          EXTRACTOR_METATYPE_GNUNET_ORIGINAL_FILENAME,
 359                                          EXTRACTOR_METAFORMAT_UTF8,
 360                                          "text/plain", tree->short_filename,
 361                                          strlen (tree->short_filename) + 1);
 362     }
 363   }
 364
 365   if (1 >= num_children)
 366     return; /* nothing to trim */
 367
 368   /* now, count keywords and meta data in children */
 369   for (pos = tree->children_head; NULL != pos; pos = pos->next)
 370   {
 371     if (NULL != pos->meta)
 372       GNUNET_CONTAINER_meta_data_iterate (pos->meta, &add_to_meta_counter, tc->metacounter);
 373     if (NULL != pos->ksk_uri)
 374       GNUNET_FS_uri_ksk_get_keywords (pos->ksk_uri, &add_to_keyword_counter, tc->keywordcounter);
 375   }
 376
 377   /* calculate threshold for moving keywords / meta data */
 378   tc->move_threshold = 1 + (num_children / 2);
 379
 380   /* remove high-frequency keywords from children */
 381   for (pos = tree->children_head; NULL != pos; pos = pos->next)
 382   {
 383     tc->pos = pos;
 384     if (NULL != pos->ksk_uri)
 385     {
 386       struct GNUNET_FS_Uri *ksk_uri_copy = GNUNET_FS_uri_dup (pos->ksk_uri);
 387       GNUNET_FS_uri_ksk_get_keywords (ksk_uri_copy, &remove_high_frequency_keywords, tc);
 388       GNUNET_FS_uri_destroy (ksk_uri_copy);
 389     }
 390   }
 391
 392   /* add high-frequency meta data and keywords to parent */
 393   tc->pos = tree;
 394   GNUNET_CONTAINER_multihashmap_iterate (tc->keywordcounter,
 395                                          &migrate_and_drop_keywords,
 396                                          tc);
 397   GNUNET_CONTAINER_multihashmap_iterate (tc->metacounter,
 398                                          &migrate_and_drop_metadata,
 399                                          tc);
 400 }
 401
 402
 403 /**
 404  * Process a share item tree, moving frequent keywords up and
 405  * copying frequent metadata up.
 406  *
 407  * @param toplevel toplevel directory in the tree, returned by the scanner
 408  */
 409 void
 410 GNUNET_FS_share_tree_trim (struct GNUNET_FS_ShareTreeItem *toplevel)
 411 {
 412   struct TrimContext tc;
 413
 414   if (toplevel == NULL)
 415     return;
 416   tc.keywordcounter = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_NO);
 417   tc.metacounter = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_NO);
 418   share_tree_trim (&tc, toplevel);
 419   GNUNET_CONTAINER_multihashmap_destroy (tc.keywordcounter);
 420   GNUNET_CONTAINER_multihashmap_destroy (tc.metacounter);
 421 }
 422
 423
 424 /**
 425  * Release memory of a share item tree.
 426  *
 427  * @param toplevel toplevel of the tree to be freed
 428  */
 429 void
 430 GNUNET_FS_share_tree_free (struct GNUNET_FS_ShareTreeItem *toplevel)
 431 {
 432   struct GNUNET_FS_ShareTreeItem *pos;
 433
 434   while (NULL != (pos = toplevel->children_head))
 435     GNUNET_FS_share_tree_free (pos);
 436   if (NULL != toplevel->parent)
 437     GNUNET_CONTAINER_DLL_remove (toplevel->parent->children_head,
 438                                  toplevel->parent->children_tail,
 439                                  toplevel);
 440   if (NULL != toplevel->meta)
 441     GNUNET_CONTAINER_meta_data_destroy (toplevel->meta);
 442   if (NULL != toplevel->ksk_uri)
 443     GNUNET_FS_uri_destroy (toplevel->ksk_uri);
 444   GNUNET_free_non_null (toplevel->filename);
 445   GNUNET_free_non_null (toplevel->short_filename);
 446   GNUNET_free (toplevel);
 447 }
 448
 449 /* end fs_sharetree.c */
 450