src/fs/fs_search.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2001, 2002, 2003, 2004, 2005, 2006, 2008 Christian Grothoff (and other contributing authors)
   4
   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.
   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      General Public License for more details.
  14
  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.
  19 */
  20
  21 /**
  22  * @file fs/fs_search.c
  23  * @brief Helper functions for searching.
  24  * @author Christian Grothoff
  25  */
  26
  27 #include "platform.h"
  28 #include "gnunet_fs_service.h"
  29 #include "fs.h"
  30
  31 #define DEBUG_SEARCH GNUNET_YES
  32
  33
  34 /**
  35  * Start search for content.
  36  *
  37  * @param h handle to the file sharing subsystem
  38  * @param uri specifies the search parameters; can be
  39  *        a KSK URI or an SKS URI.
  40  * @param anonymity desired level of anonymity
  41  * @return context that can be used to control the search
  42  */
  43 struct GNUNET_FS_SearchContext *
  44 GNUNET_FS_search_start (struct GNUNET_FS_Handle *h,
  45                         const struct GNUNET_FS_Uri *uri,
  46                         unsigned int anonymity)
  47 {
  48   return NULL;
  49 }
  50
  51
  52 /**
  53  * Pause search.
  54  *
  55  * @param sc context for the search that should be paused
  56  */
  57 void
  58 GNUNET_FS_search_pause (struct GNUNET_FS_SearchContext *sc)
  59 {
  60 }
  61
  62 /**
  63  * Continue paused search.
  64  *
  65  * @param sc context for the search that should be resumed
  66  */
  67 void
  68 GNUNET_FS_search_continue (struct GNUNET_FS_SearchContext *sc)
  69 {
  70 }
  71
  72
  73 /**
  74  * Stop search for content.
  75  *
  76  * @param sc context for the search that should be stopped
  77  */
  78 void
  79 GNUNET_FS_search_stop (struct GNUNET_FS_SearchContext *sc)
  80 {
  81 }
  82
  83
  84
  85
  86 #if 0
  87
  88 /**
  89  * Context for an individual search.  Followed
  90  *  by keyCount keys of type GNUNET_HashCode.
  91  */
  92 struct PendingSearch
  93 {
  94   struct PendingSearch *next;
  95
  96   struct GNUNET_ECRS_SearchContext *context;
  97
  98   /**
  99    * The key (for decryption)
 100    */
 101   GNUNET_HashCode decryptKey;
 102
 103   unsigned int keyCount;
 104
 105   /**
 106    * What type of query is it?
 107    */
 108   unsigned int type;
 109
 110 };
 111
 112 /**
 113  * Context for search operation.
 114  */
 115 struct GNUNET_ECRS_SearchContext
 116 {
 117   /**
 118    * Time when the cron-job was first started.
 119    */
 120   GNUNET_CronTime start;
 121
 122   /**
 123    * What is the global timeout?
 124    */
 125   GNUNET_CronTime timeout;
 126
 127   /**
 128    * Search context
 129    */
 130   struct GNUNET_FS_SearchContext *sctx;
 131
 132   /**
 133    * Active searches.
 134    */
 135   struct PendingSearch *queries;
 136
 137   GNUNET_ECRS_SearchResultProcessor spcb;
 138
 139   void *spcbClosure;
 140
 141   struct GNUNET_GE_Context *ectx;
 142
 143   struct GNUNET_GC_Configuration *cfg;
 144
 145   int aborted;
 146
 147   int my_sctx;
 148
 149   unsigned int anonymityLevel;
 150
 151 };
 152
 153 static int
 154 receive_response_callback (const GNUNET_HashCode * key,
 155                            const GNUNET_DatastoreValue * value,
 156                            void *cls, unsigned long long uid);
 157
 158 /**
 159  * Add a query to the SQC.
 160  */
 161 static void
 162 add_search (unsigned int type,
 163             unsigned int keyCount,
 164             const GNUNET_HashCode * keys,
 165             const GNUNET_HashCode * dkey,
 166             struct GNUNET_ECRS_SearchContext *sqc)
 167 {
 168   struct PendingSearch *ps;
 169
 170   ps =
 171     GNUNET_malloc (sizeof (struct PendingSearch) +
 172                    sizeof (GNUNET_HashCode) * keyCount);
 173   ps->type = type;
 174   ps->keyCount = keyCount;
 175   memcpy (&ps[1], keys, sizeof (GNUNET_HashCode) * keyCount);
 176   ps->decryptKey = *dkey;
 177   ps->context = sqc;
 178   ps->next = sqc->queries;
 179   sqc->queries = ps;
 180   GNUNET_FS_start_search (sqc->sctx,
 181                           NULL,
 182                           type,
 183                           keyCount,
 184                           keys,
 185                           sqc->anonymityLevel,
 186                           &receive_response_callback, ps);
 187 }
 188
 189 /**
 190  * Add the query that corresponds to the given URI
 191  * to the SQC.
 192  */
 193 static void
 194 add_search_for_uri (const struct GNUNET_ECRS_URI *uri,
 195                     struct GNUNET_ECRS_SearchContext *sqc)
 196 {
 197   struct GNUNET_GE_Context *ectx = sqc->ectx;
 198
 199   switch (uri->type)
 200     {
 201     case chk:
 202       GNUNET_GE_LOG (ectx,
 203                      GNUNET_GE_ERROR | GNUNET_GE_BULK | GNUNET_GE_USER,
 204                      _("CHK URI not allowed for search.\n"));
 205       break;
 206     case sks:
 207       {
 208         GNUNET_HashCode keys[2];
 209         GNUNET_HashCode hk;     /* hk = GNUNET_hash(identifier) */
 210         GNUNET_HashCode hk2;    /* hk2 = GNUNET_hash(hk) */
 211
 212         GNUNET_hash (uri->data.sks.identifier,
 213                      strlen (uri->data.sks.identifier), &hk);
 214         GNUNET_hash (&hk, sizeof (GNUNET_HashCode), &hk2);
 215         /* compute routing key keys[0] = H(key) ^ namespace */
 216         GNUNET_hash_xor (&hk2, &uri->data.sks.namespace, &keys[0]);
 217         keys[1] = uri->data.sks.namespace;
 218         add_search (GNUNET_ECRS_BLOCKTYPE_SIGNED, 2, &keys[0], &hk, sqc);
 219         break;
 220       }
 221     case ksk:
 222       {
 223         GNUNET_HashCode hc;
 224         GNUNET_HashCode query;
 225         struct GNUNET_RSA_PrivateKey *pk;
 226         GNUNET_RSA_PublicKey pub;
 227         int i;
 228         const char *keyword;
 229
 230 #if DEBUG_SEARCH
 231         GNUNET_GE_LOG (ectx,
 232                        GNUNET_GE_DEBUG | GNUNET_GE_REQUEST | GNUNET_GE_USER,
 233                        "Computing queries (this may take a while).\n");
 234 #endif
 235         for (i = 0; i < uri->data.ksk.keywordCount; i++)
 236           {
 237             keyword = uri->data.ksk.keywords[i];
 238             /* first character of the keyword is
 239                "+" or " " to indicate mandatory or
 240                not -- ignore for hashing! */
 241             GNUNET_hash (&keyword[1], strlen (&keyword[1]), &hc);
 242             pk = GNUNET_RSA_create_key_from_hash (&hc);
 243             GNUNET_RSA_get_public_key (pk, &pub);
 244             GNUNET_hash (&pub, sizeof (GNUNET_RSA_PublicKey), &query);
 245             add_search (GNUNET_ECRS_BLOCKTYPE_ANY,      /* GNUNET_ECRS_BLOCKTYPE_KEYWORD, GNUNET_ECRS_BLOCKTYPE_NAMESPACE or GNUNET_ECRS_BLOCKTYPE_KEYWORD_FOR_NAMESPACE ok */
 246                         1, &query, &hc, sqc);
 247             GNUNET_RSA_free_key (pk);
 248           }
 249 #if DEBUG_SEARCH
 250         GNUNET_GE_LOG (ectx,
 251                        GNUNET_GE_DEBUG | GNUNET_GE_REQUEST | GNUNET_GE_USER,
 252                        "Queries ready.\n");
 253 #endif
 254         break;
 255       }
 256     case loc:
 257       GNUNET_GE_LOG (ectx,
 258                      GNUNET_GE_ERROR | GNUNET_GE_BULK | GNUNET_GE_USER,
 259                      _("LOC URI not allowed for search.\n"));
 260       break;
 261     default:
 262       GNUNET_GE_BREAK (ectx, 0);
 263       /* unknown URI type */
 264       break;
 265     }
 266 }
 267
 268 /**
 269  * We found an GNUNET_EC_SBlock.  Decode the meta-data and call
 270  * the callback of the SQC with the root-URI for the namespace,
 271  * together with the namespace advertisement.  Also, if this is
 272  * a result with updates, automatically start the search for
 273  * updates.
 274  */
 275 static int
 276 process_sblock_result (const GNUNET_EC_SBlock * sb,
 277                        const GNUNET_HashCode * key,
 278                        unsigned int size,
 279                        struct GNUNET_ECRS_SearchContext *sqc)
 280 {
 281   static GNUNET_HashCode allZeros;
 282   struct GNUNET_GE_Context *ectx = sqc->ectx;
 283   GNUNET_ECRS_FileInfo fi;
 284   URI updateURI;
 285   int ret;
 286   const char *id;
 287   const char *uris;
 288   unsigned int len;
 289   unsigned int off;
 290   int isRoot;
 291
 292   len = size - sizeof (GNUNET_EC_SBlock);
 293   off = GNUNET_string_buffer_tokenize ((const char *) &sb[1],
 294                                        len, 2, &id, &uris);
 295   if (off == 0)
 296     {
 297       GNUNET_GE_BREAK_OP (ectx, 0);     /* sblock malformed */
 298       return GNUNET_SYSERR;
 299     }
 300   fi.meta = GNUNET_meta_data_deserialize (ectx, &id[off], len - off);
 301   if (fi.meta == NULL)
 302     {
 303       GNUNET_GE_BREAK_OP (ectx, 0);     /* sblock malformed */
 304       return GNUNET_SYSERR;
 305     }
 306   isRoot = 0 == memcmp (&sb->identifier, &allZeros, sizeof (GNUNET_HashCode));
 307   fi.uri = GNUNET_ECRS_string_to_uri (ectx, uris);
 308   if ((isRoot) && (fi.uri == NULL))
 309     {
 310       fi.uri = GNUNET_malloc (sizeof (URI));
 311       fi.uri->type = sks;
 312       GNUNET_hash (&sb->subspace,
 313                    sizeof (GNUNET_RSA_PublicKey),
 314                    &fi.uri->data.sks.namespace);
 315       fi.uri->data.sks.identifier = GNUNET_strdup (id);
 316     }
 317   if (fi.uri == NULL)
 318     {
 319       GNUNET_GE_BREAK_OP (ectx, 0);     /* sblock malformed */
 320       GNUNET_meta_data_destroy (fi.meta);
 321       return GNUNET_SYSERR;
 322     }
 323   if (sqc->spcb != NULL)
 324     {
 325       ret = sqc->spcb (&fi, key, isRoot, sqc->spcbClosure);
 326       if (ret == GNUNET_SYSERR)
 327         sqc->aborted = GNUNET_YES;
 328     }
 329   else
 330     ret = GNUNET_OK;
 331   if ((strlen (id) > 0) && (strlen (uris) > 0))
 332     {
 333       updateURI.type = sks;
 334       GNUNET_hash (&sb->subspace,
 335                    sizeof (GNUNET_RSA_PublicKey),
 336                    &updateURI.data.sks.namespace);
 337       updateURI.data.sks.identifier = GNUNET_strdup (id);
 338       add_search_for_uri (&updateURI, sqc);
 339       GNUNET_free (updateURI.data.sks.identifier);
 340     }
 341   GNUNET_meta_data_destroy (fi.meta);
 342   GNUNET_ECRS_uri_destroy (fi.uri);
 343   return ret;
 344 }
 345
 346 /**
 347  * Process replies received in response to our
 348  * queries.  Verifies, decrypts and passes valid
 349  * replies to the callback.
 350  *
 351  * @return GNUNET_SYSERR if the entry is malformed
 352  */
 353 static int
 354 receive_response_callback (const GNUNET_HashCode * key,
 355                            const GNUNET_DatastoreValue * value,
 356                            void *cls, unsigned long long uid)
 357 {
 358   struct PendingSearch *ps = cls;
 359   struct GNUNET_ECRS_SearchContext *sqc = ps->context;
 360   struct GNUNET_GE_Context *ectx = sqc->ectx;
 361   unsigned int type;
 362   GNUNET_ECRS_FileInfo fi;
 363   unsigned int size;
 364   int ret;
 365   GNUNET_HashCode query;
 366   GNUNET_CronTime expiration;
 367
 368   expiration = GNUNET_ntohll (value->expiration_time);
 369   if (expiration < GNUNET_get_time ())
 370     return GNUNET_OK;           /* expired, ignore! */
 371   type = ntohl (value->type);
 372   size = ntohl (value->size) - sizeof (GNUNET_DatastoreValue);
 373 #if DEBUG_SEARCH
 374   GNUNET_GE_LOG (ectx,
 375                  GNUNET_GE_DEBUG | GNUNET_GE_REQUEST | GNUNET_GE_USER,
 376                  "Search received reply of type %u and size %u.\n", type,
 377                  size);
 378 #endif
 379   if (GNUNET_OK !=
 380       GNUNET_EC_file_block_check_and_get_query (size,
 381                                                 (const GNUNET_EC_DBlock *)
 382                                                 &value[1], GNUNET_YES,
 383                                                 &query))
 384     {
 385       GNUNET_GE_BREAK_OP (NULL, 0);
 386       return GNUNET_SYSERR;
 387     }
 388   if (!((0 == memcmp (&query,
 389                       (GNUNET_HashCode *) & ps[1], sizeof (GNUNET_HashCode)))
 390         && ((ps->type == type) || (ps->type == GNUNET_ECRS_BLOCKTYPE_ANY))
 391         && (GNUNET_YES ==
 392             GNUNET_EC_is_block_applicable_for_query (type, size,
 393                                                      (const GNUNET_EC_DBlock
 394                                                       *) &value[1], &query,
 395                                                      ps->keyCount,
 396                                                      (GNUNET_HashCode *) &
 397                                                      ps[1]))))
 398     {
 399       return GNUNET_OK;         /* not a match */
 400     }
 401
 402   switch (type)
 403     {
 404     case GNUNET_ECRS_BLOCKTYPE_KEYWORD:
 405       {
 406         GNUNET_EC_KBlock *kb;
 407         const char *dstURI;
 408 #if DEBUG_SEARCH
 409         GNUNET_EncName enc;
 410 #endif
 411         int j;
 412
 413         if (size < sizeof (GNUNET_EC_KBlock))
 414           {
 415             GNUNET_GE_BREAK_OP (NULL, 0);
 416             return GNUNET_SYSERR;
 417           }
 418         kb = GNUNET_malloc (size);
 419         memcpy (kb, &value[1], size);
 420 #if DEBUG_SEARCH
 421         IF_GELOG (ectx,
 422                   GNUNET_GE_DEBUG | GNUNET_GE_REQUEST |
 423                   GNUNET_GE_USER, GNUNET_hash_to_enc (&ps->decryptKey, &enc));
 424         GNUNET_GE_LOG (ectx,
 425                        GNUNET_GE_DEBUG | GNUNET_GE_REQUEST |
 426                        GNUNET_GE_USER,
 427                        "Decrypting KBlock with key %s.\n", &enc);
 428 #endif
 429         GNUNET_ECRS_decryptInPlace (&ps->decryptKey,
 430                                     &kb[1], size - sizeof (GNUNET_EC_KBlock));
 431         j = sizeof (GNUNET_EC_KBlock);
 432         while ((j < size) && (((const char *) kb)[j] != '\0'))
 433           j++;
 434         if (j == size)
 435           {
 436             GNUNET_GE_BREAK_OP (ectx, 0);       /* kblock malformed */
 437             GNUNET_free (kb);
 438             return GNUNET_SYSERR;
 439           }
 440         dstURI = (const char *) &kb[1];
 441         j++;
 442         fi.meta = GNUNET_meta_data_deserialize (ectx,
 443                                                 &((const char *)
 444                                                   kb)[j], size - j);
 445         if (fi.meta == NULL)
 446           {
 447             GNUNET_GE_BREAK_OP (ectx, 0);       /* kblock malformed */
 448             GNUNET_free (kb);
 449             return GNUNET_SYSERR;
 450           }
 451         fi.uri = GNUNET_ECRS_string_to_uri (ectx, dstURI);
 452         if (fi.uri == NULL)
 453           {
 454             GNUNET_GE_BREAK_OP (ectx, 0);       /* kblock malformed */
 455             GNUNET_meta_data_destroy (fi.meta);
 456             GNUNET_free (kb);
 457             return GNUNET_SYSERR;
 458           }
 459         if (sqc->spcb != NULL)
 460           {
 461             ret = sqc->spcb (&fi,
 462                              &ps->decryptKey, GNUNET_NO, sqc->spcbClosure);
 463             if (ret == GNUNET_SYSERR)
 464               sqc->aborted = GNUNET_YES;
 465           }
 466         else
 467           ret = GNUNET_OK;
 468         GNUNET_ECRS_uri_destroy (fi.uri);
 469         GNUNET_meta_data_destroy (fi.meta);
 470         GNUNET_free (kb);
 471         return ret;
 472       }
 473     case GNUNET_ECRS_BLOCKTYPE_SIGNED:
 474       {
 475         GNUNET_EC_SBlock *sb;
 476         int ret;
 477
 478         if (size < sizeof (GNUNET_EC_SBlock))
 479           {
 480             GNUNET_GE_BREAK_OP (ectx, 0);       /* sblock malformed */
 481             return GNUNET_SYSERR;
 482           }
 483         sb = GNUNET_malloc (size);
 484         memcpy (sb, &value[1], size);
 485         GNUNET_ECRS_decryptInPlace (&ps->decryptKey,
 486                                     &sb[1], size - sizeof (GNUNET_EC_SBlock));
 487         ret = process_sblock_result (sb, &ps->decryptKey, size, sqc);
 488         GNUNET_free (sb);
 489         return ret;
 490       }
 491     case GNUNET_ECRS_BLOCKTYPE_KEYWORD_SIGNED:
 492       {
 493         GNUNET_EC_KSBlock *kb;
 494         int ret;
 495
 496         if (size < sizeof (GNUNET_EC_KSBlock))
 497           {
 498             GNUNET_GE_BREAK_OP (ectx, 0);       /* ksblock malformed */
 499             return GNUNET_SYSERR;
 500           }
 501         kb = GNUNET_malloc (size);
 502         memcpy (kb, &value[1], size);
 503         GNUNET_ECRS_decryptInPlace (&ps->decryptKey,
 504                                     &kb->sblock,
 505                                     size - sizeof (GNUNET_EC_KBlock) -
 506                                     sizeof (unsigned int));
 507         ret =
 508           process_sblock_result (&kb->sblock, &ps->decryptKey,
 509                                  size - sizeof (GNUNET_EC_KSBlock) +
 510                                  sizeof (GNUNET_EC_SBlock), sqc);
 511         GNUNET_free (kb);
 512         return ret;
 513       }
 514     default:
 515       GNUNET_GE_BREAK_OP (ectx, 0);
 516       break;
 517     }                           /* end switch */
 518   return GNUNET_OK;
 519 }
 520
 521 /**
 522  * Start search for content.
 523  *
 524  * @param uri specifies the search parameters
 525  * @param uri set to the URI of the uploaded file
 526  */
 527 struct GNUNET_ECRS_SearchContext *
 528 GNUNET_ECRS_search_start (struct GNUNET_GE_Context *ectx,
 529                           struct GNUNET_GC_Configuration *cfg,
 530                           struct GNUNET_FS_SearchContext *sc,
 531                           const struct GNUNET_ECRS_URI *uri,
 532                           unsigned int anonymityLevel,
 533                           GNUNET_ECRS_SearchResultProcessor spcb,
 534                           void *spcbClosure)
 535 {
 536   struct GNUNET_ECRS_SearchContext *ctx;
 537
 538   if (GNUNET_YES == GNUNET_ECRS_uri_test_ksk (uri))
 539     {
 540       if (1 != GNUNET_ECRS_uri_get_keyword_count_from_ksk (uri))
 541         return NULL;
 542     }
 543   else
 544     {
 545       if (GNUNET_YES != GNUNET_ECRS_uri_test_sks (uri))
 546         return NULL;
 547     }
 548   ctx = GNUNET_malloc (sizeof (struct GNUNET_ECRS_SearchContext));
 549   ctx->start = GNUNET_get_time ();
 550   ctx->anonymityLevel = anonymityLevel;
 551   ctx->ectx = ectx;
 552   ctx->cfg = cfg;
 553   ctx->queries = NULL;
 554   ctx->spcb = spcb;
 555   ctx->spcbClosure = spcbClosure;
 556   ctx->aborted = GNUNET_NO;
 557   ctx->sctx = sc == NULL ? GNUNET_FS_create_search_context (ectx, cfg) : sc;
 558   if (ctx->sctx == NULL)
 559     {
 560       GNUNET_free (ctx);
 561       return NULL;
 562     }
 563   ctx->my_sctx = (sc == NULL);
 564   add_search_for_uri (uri, ctx);
 565   return ctx;
 566 }
 567
 568 /**
 569  * Stop search for content.
 570  *
 571  * @param uri specifies the search parameters
 572  * @param uri set to the URI of the uploaded file
 573  */
 574 void
 575 GNUNET_ECRS_search_stop (struct GNUNET_ECRS_SearchContext *ctx)
 576 {
 577   struct PendingSearch *pos;
 578
 579   while (ctx->queries != NULL)
 580     {
 581       pos = ctx->queries;
 582       ctx->queries = pos->next;
 583       if (!ctx->my_sctx)
 584         GNUNET_FS_stop_search (ctx->sctx, &receive_response_callback, pos);
 585       GNUNET_free (pos);
 586     }
 587   if (ctx->my_sctx)
 588     GNUNET_FS_destroy_search_context (ctx->sctx);
 589   GNUNET_free (ctx);
 590 }
 591
 592 /**
 593  * Search for content.
 594  *
 595  * @param timeout how long to wait (relative)
 596  * @param uri specifies the search parameters
 597  * @param uri set to the URI of the uploaded file
 598  */
 599 int
 600 GNUNET_ECRS_search (struct GNUNET_GE_Context *ectx,
 601                     struct GNUNET_GC_Configuration *cfg,
 602                     const struct GNUNET_ECRS_URI *uri,
 603                     unsigned int anonymityLevel,
 604                     GNUNET_ECRS_SearchResultProcessor spcb,
 605                     void *spcbClosure, GNUNET_ECRS_TestTerminate tt,
 606                     void *ttClosure)
 607 {
 608   struct GNUNET_ECRS_SearchContext *ctx;
 609
 610   ctx =
 611     GNUNET_ECRS_search_start (ectx, cfg, NULL,
 612                               uri, anonymityLevel, spcb, spcbClosure);
 613   if (ctx == NULL)
 614     return GNUNET_SYSERR;
 615   while (((NULL == tt) || (GNUNET_OK == tt (ttClosure)))
 616          && (GNUNET_NO == GNUNET_shutdown_test ())
 617          && (ctx->aborted == GNUNET_NO))
 618     GNUNET_thread_sleep (100 * GNUNET_CRON_MILLISECONDS);
 619   GNUNET_ECRS_search_stop (ctx);
 620   return GNUNET_OK;
 621 }
 622
 623 #endif
 624
 625 /* end of fs_search.c */