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