1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/gt_search.c	Sat Feb 20 21:18:28 2010 -0800
     1.3 @@ -0,0 +1,732 @@
     1.4 +/*
     1.5 + * $Id: gt_search.c,v 1.60 2004/11/29 12:32:12 mkern Exp $
     1.6 + *
     1.7 + * Copyright (C) 2001-2003 giFT project (gift.sourceforge.net)
     1.8 + *
     1.9 + * This program is free software; you can redistribute it and/or modify it
    1.10 + * under the terms of the GNU General Public License as published by the
    1.11 + * Free Software Foundation; either version 2, or (at your option) any
    1.12 + * later version.
    1.13 + *
    1.14 + * This program is distributed in the hope that it will be useful, but
    1.15 + * WITHOUT ANY WARRANTY; without even the implied warranty of
    1.16 + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    1.17 + * General Public License for more details.
    1.18 + */
    1.19 +
    1.20 +#include "gt_gnutella.h"
    1.21 +
    1.22 +#include "gt_node.h"
    1.23 +#include "gt_node_list.h"
    1.24 +#include "gt_share.h"
    1.25 +#include "gt_share_file.h"
    1.26 +#include "gt_packet.h"
    1.27 +#include "gt_search.h"
    1.28 +#include "gt_xfer.h"
    1.29 +
    1.30 +#include "sha1.h"
    1.31 +
    1.32 +#include "encoding/url.h"           /* gt_url_decode */
    1.33 +
    1.34 +#include "transfer/download.h"
    1.35 +#include "transfer/source.h"
    1.36 +
    1.37 +#include <libgift/mime.h>
    1.38 +
    1.39 +/******************************************************************************/
    1.40 +
    1.41 +/* how often we check if the search has timed out */
    1.42 +#define   TIMEOUT_CHECK_INTERVAL (20 * SECONDS)
    1.43 +
    1.44 +/* after this many results, no more search submissions will occur */
    1.45 +#define   RESULTS_BACKOFF        (200)
    1.46 +
    1.47 +/*
    1.48 + * Gnutella searches don't notify when they are done. So, we close the
    1.49 + * search after the following critieria are met:
    1.50 + *
    1.51 + *   - we have submitted the search to at least 3 Ultrapeers
    1.52 + *     [MIN_NODES]
    1.53 + *   - at least 3 minutes have passed since we last submitted to an ultrapeer
    1.54 + *     [MIN_SUBMIT_WAIT]
    1.55 + *   - no results have been seen in the last minute
    1.56 + *     [MIN_RESULT_WAIT]
    1.57 + *
    1.58 + * This means the fastest we'll time out a search is 3 minutes if
    1.59 + * we submit to 3 ultrapeers immediately and get no results within
    1.60 + * 1 minute of the 3 minute time limit.
    1.61 + *
    1.62 + * For hash searches, we wait for 2 * MIN_SUBMIT_WAIT, because the other
    1.63 + * factors won't come into play.
    1.64 + *
    1.65 + * There is also a large timeout for searches that receive no results
    1.66 + * [ANCIENT_TIME].  Searches that exceed this age and haven't received
    1.67 + * any results in the same time will automatically be cancelled, regardless of
    1.68 + * other critieria.
    1.69 + */
    1.70 +#define MIN_NODES             (3)             /* ultrapeers */
    1.71 +#define MIN_SUBMIT_WAIT       (3 * EMINUTES)
    1.72 +#define MIN_RESULT_WAIT       (1 * EMINUTES)
    1.73 +#define ANCIENT_TIME          (10 * EMINUTES)
    1.74 +
    1.75 +/******************************************************************************/
    1.76 +
    1.77 +/* active keyword and hash searches from this node */
    1.78 +static List   *active_searches;
    1.79 +
    1.80 +/* probability of the next hash search not being dropped */
    1.81 +static double  locate_pass_prob;
    1.82 +
    1.83 +/******************************************************************************/
    1.84 +
    1.85 +static BOOL finish_search (GtSearch *search)
    1.86 +{
    1.87 +	GT->DBGFN (GT, "search query for \"%s\" timed out", search->query);
    1.88 +	gt_search_free (search);
    1.89 +	return FALSE;
    1.90 +}
    1.91 +
    1.92 +static BOOL search_is_ancient (GtSearch *search, time_t now)
    1.93 +{
    1.94 +	if (difftime (now, search->start) < ANCIENT_TIME)
    1.95 +		return FALSE;
    1.96 +
    1.97 +	/*
    1.98 +	 * If the search is greater than ANCIENT_TIME and hasn't received
    1.99 +	 * a result in the same time, consider it ancient.
   1.100 +	 */
   1.101 +	if (search->last_result == 0)
   1.102 +		return TRUE;
   1.103 +
   1.104 +	if (difftime (now, search->last_result) >= ANCIENT_TIME)
   1.105 +		return TRUE;
   1.106 +
   1.107 +	return FALSE;
   1.108 +}
   1.109 +
   1.110 +/*
   1.111 + * search_timeout: check if the search needs to be closed.
   1.112 + *
   1.113 + * Its impossible to guarantee this will not close the search too early.
   1.114 + * It is more likely to miss results if bandwidth is being dedicated to
   1.115 + * other purposes besides reading Gnutella messages, or if the TTL and
   1.116 + * consequently the latency of the search is high.
   1.117 + *
   1.118 + * TODO: this should take into account that we may have disconnected
   1.119 + *       from the nodes we submitted the search to. Perhaps, have
   1.120 + *       a list of the submitted nodes, and make sure the list len >=
   1.121 + *       MIN_NODES (but this may run into trouble with not submitting
   1.122 + *       searches with results >= RESULTS_BACKOFF...)
   1.123 + */
   1.124 +static BOOL search_timeout (GtSearch *search)
   1.125 +{
   1.126 +	time_t now;
   1.127 +	double submit_wait;
   1.128 +	double result_wait;
   1.129 +
   1.130 +	time (&now);
   1.131 +
   1.132 +	/* check if this search is really old and should be expired */
   1.133 +	if (search_is_ancient (search, now))
   1.134 +		return finish_search (search);
   1.135 +
   1.136 +	if (search->submitted < MIN_NODES)
   1.137 +		return TRUE;
   1.138 +
   1.139 +	submit_wait = MIN_SUBMIT_WAIT;
   1.140 +	result_wait = MIN_RESULT_WAIT;
   1.141 +
   1.142 +	/* hash searches get very few results, so give them a longer base time */
   1.143 +	if (search->type == GT_SEARCH_HASH)
   1.144 +		submit_wait *= 2;
   1.145 +
   1.146 +	/*
   1.147 +	 * If the search has lots of results, don't wait as long.
   1.148 +	 *
   1.149 +	 * RESULTS_BACKOFF is a conservative value for not submitting to other
   1.150 +	 * nodes when we already have plenty of results, and we want to be a
   1.151 +	 * little less conservative here, so multiply RESULTS_BACKOFF by 2.
   1.152 +	 */
   1.153 +	if (search->results >= 2 * RESULTS_BACKOFF)
   1.154 +	{
   1.155 +		submit_wait /= 2;
   1.156 +		result_wait /= 2;
   1.157 +	}
   1.158 +
   1.159 +	if (difftime (now, search->last_submit) < submit_wait)
   1.160 +		return TRUE;
   1.161 +
   1.162 +	if (difftime (now, search->last_result) < result_wait)
   1.163 +		return TRUE;
   1.164 +
   1.165 +	/* the search has timed out */
   1.166 +	return finish_search (search);
   1.167 +}
   1.168 +
   1.169 +/*****************************************************************************/
   1.170 +
   1.171 +GtSearch *gt_search_new (IFEvent *event, char *query, gt_search_type_t type)
   1.172 +{
   1.173 +	GtSearch *search;
   1.174 +
   1.175 +	if (!(search = malloc (sizeof (GtSearch))))
   1.176 +		return NULL;
   1.177 +
   1.178 +	memset (search, 0, sizeof (GtSearch));
   1.179 +
   1.180 +	search->event   = event;
   1.181 +	search->type    = type;
   1.182 +	search->guid    = gt_guid_new ();
   1.183 +	search->query   = STRDUP (query);
   1.184 +	search->results = 0;
   1.185 +	search->start   = time (NULL);
   1.186 +
   1.187 +	search->timeout_timer = timer_add (TIMEOUT_CHECK_INTERVAL,
   1.188 +	                                   (TimerCallback)search_timeout,
   1.189 +	                                   search);
   1.190 +
   1.191 +	GT->DBGFN (GT, "new search \"%s\"", query);
   1.192 +
   1.193 +	active_searches = list_prepend (active_searches, search);
   1.194 +
   1.195 +	return search;
   1.196 +}
   1.197 +
   1.198 +void gt_search_free (GtSearch *search)
   1.199 +{
   1.200 +	if (!search)
   1.201 +		return;
   1.202 +
   1.203 +	if (!list_find (active_searches, search))
   1.204 +	{
   1.205 +		GIFT_ERROR (("couldn't find search %p (query:'%s')",
   1.206 +		              search, search->query));
   1.207 +		return;
   1.208 +	}
   1.209 +
   1.210 +	if (search->timeout_timer)
   1.211 +		timer_remove (search->timeout_timer);
   1.212 +
   1.213 +	if (search->event)
   1.214 +		GT->search_complete (GT, search->event);
   1.215 +
   1.216 +	/* NOTE: search_complete may have removed the search by calling
   1.217 +	 * gt_search_disable */
   1.218 +	active_searches = list_remove (active_searches, search);
   1.219 +
   1.220 +	free (search->hash);
   1.221 +	free (search->realm);
   1.222 +	free (search->guid);
   1.223 +	free (search->query);
   1.224 +	free (search);
   1.225 +}
   1.226 +
   1.227 +static int find_by_event (GtSearch *search, IFEvent *event)
   1.228 +{
   1.229 +	if (search->event == event)
   1.230 +		return 0;
   1.231 +
   1.232 +	return -1;
   1.233 +}
   1.234 +
   1.235 +void gt_search_disable (IFEvent *event)
   1.236 +{
   1.237 +	List      *ls;
   1.238 +	GtSearch  *search;
   1.239 +
   1.240 +	ls = list_find_custom (active_searches, event,
   1.241 +	                       (CompareFunc) find_by_event);
   1.242 +
   1.243 +	if (!ls)
   1.244 +	{
   1.245 +		GT->DBGFN (GT, "didnt find search id %p", (long) event);
   1.246 +		return;
   1.247 +	}
   1.248 +
   1.249 +	search = ls->data;
   1.250 +
   1.251 +	GT->DBGFN (GT, "disabled search event %p (query '%s')", event, search->query);
   1.252 +	search->event = NULL;
   1.253 +}
   1.254 +
   1.255 +/******************************************************************************/
   1.256 +
   1.257 +static int find_by_guid (GtSearch *a, GtSearch *b)
   1.258 +{
   1.259 +	return gt_guid_cmp (a->guid, b->guid);
   1.260 +}
   1.261 +
   1.262 +GtSearch *gt_search_find (gt_guid_t *guid)
   1.263 +{
   1.264 +	GtSearch  key;
   1.265 +	List     *l;
   1.266 +
   1.267 +	key.guid = guid;
   1.268 +
   1.269 +	l = list_find_custom (active_searches, &key, (CompareFunc) find_by_guid);
   1.270 +
   1.271 +	if (!l)
   1.272 +		return NULL;
   1.273 +
   1.274 +	return l->data;
   1.275 +}
   1.276 +
   1.277 +static BOOL search_matches_realm (GtSearch *search, GtShare *share)
   1.278 +{
   1.279 +	char *mime;
   1.280 +
   1.281 +	if (!search->realm)
   1.282 +		return TRUE;
   1.283 +
   1.284 +	if (!(mime = mime_type (share->filename)))
   1.285 +		return FALSE;
   1.286 +
   1.287 +	if (strstr (mime, search->realm))
   1.288 +		return TRUE;
   1.289 +
   1.290 +	if (!STRCMP (search->realm, "text"))
   1.291 +	{
   1.292 +		/* HACK: special case application/pdf */
   1.293 +		if (strstr (mime, "pdf"))
   1.294 +			return TRUE;
   1.295 +
   1.296 +		/* HACK: special case application/msword */
   1.297 +		if (strstr (mime, "doc"))
   1.298 +			return TRUE;
   1.299 +	}
   1.300 +
   1.301 +	return FALSE;
   1.302 +}
   1.303 +
   1.304 +static BOOL search_matches_hash (GtSearch *search, Share *file)
   1.305 +{
   1.306 +	Hash *hash;
   1.307 +	char *str;
   1.308 +	int   ret;
   1.309 +
   1.310 +	if (search->type != GT_SEARCH_HASH)
   1.311 +		return TRUE;
   1.312 +
   1.313 +	if (!(hash = share_get_hash (file, "SHA1")))
   1.314 +	{
   1.315 +		GT->DBGFN (GT, "bad result for hash query");
   1.316 +		return FALSE;
   1.317 +	}
   1.318 +
   1.319 +	if (!(str = hash_dsp (hash)))
   1.320 +		return FALSE;
   1.321 +
   1.322 +	ret = strcmp (search->hash, hashstr_data (str));
   1.323 +
   1.324 +	free (str);
   1.325 +
   1.326 +	return (ret == 0);
   1.327 +}
   1.328 +
   1.329 +/*
   1.330 + * We have to filter out backslashes from the name to workaround a bug
   1.331 + * in lib/file.c.
   1.332 + */
   1.333 +static void set_display_name (Share *share, const char *path)
   1.334 +{
   1.335 +	char *p;
   1.336 +	char *disp_name;
   1.337 +
   1.338 +	if (!(p = disp_name = STRDUP (path)))
   1.339 +		return;
   1.340 +
   1.341 +	while (*p)
   1.342 +	{
   1.343 +		if (*p == '\\')
   1.344 +			*p = '_';
   1.345 +		p++;
   1.346 +	}
   1.347 +
   1.348 +	/* NOTE: this makes the GtShare->filename invalid because it shares memory
   1.349 +	 * with the Share */
   1.350 +	share_set_path (share, disp_name);
   1.351 +	free (disp_name);
   1.352 +}
   1.353 +
   1.354 +void gt_search_reply (GtSearch *search, TCPC *c, in_addr_t host,
   1.355 +                      in_port_t gt_port, gt_guid_t *client_guid,
   1.356 +                      int availability, BOOL firewalled,
   1.357 +                      FileShare *file)
   1.358 +{
   1.359 +	char       server[128];
   1.360 +	char      *url;
   1.361 +	char      *host_str;
   1.362 +	char      *path;
   1.363 +	GtShare   *share;
   1.364 +	GtNode    *node;
   1.365 +	BOOL       is_local;
   1.366 +
   1.367 +	node = GT_NODE(c);
   1.368 +
   1.369 +	if (!search->event)
   1.370 +		return;
   1.371 +
   1.372 +	if (gt_is_local_ip (host, node->ip))
   1.373 +		is_local = TRUE;
   1.374 +	else
   1.375 +		is_local = FALSE;
   1.376 +
   1.377 +	/* derive firewalled status if the address is local */
   1.378 +	if (is_local)
   1.379 +		firewalled = TRUE;
   1.380 +
   1.381 +	/* if they are firewalled and so are we, don't bother.
   1.382 +	 * NOTE: if we have a download proxy, we shouldnt do this */
   1.383 +	if (firewalled && GT_SELF->firewalled)
   1.384 +		return;
   1.385 +
   1.386 +	if (!(share = share_get_udata (file, GT->name)))
   1.387 +		return;
   1.388 +
   1.389 +	/* check if the mimetype for the result matches the query (i.e. this does
   1.390 +	 * client-side filtering) */
   1.391 +	if (!search_matches_realm (search, share))
   1.392 +		return;
   1.393 +
   1.394 +	/* match against the hash if this is a hash search */
   1.395 +	if (!search_matches_hash (search, file))
   1.396 +		return;
   1.397 +
   1.398 +	/* get the whole path (result may have '/' separators) */
   1.399 +	path = file->path;
   1.400 +	assert (path != NULL);
   1.401 +
   1.402 +	url = gt_source_url_new (path, share->index, host, gt_port,
   1.403 +	                         node->ip, node->gt_port,
   1.404 +	                         firewalled, client_guid);
   1.405 +
   1.406 +	if (!url)
   1.407 +		return;
   1.408 +
   1.409 +	/* workaround bug in lib/file.c */
   1.410 +	set_display_name (file, path);
   1.411 +
   1.412 +	/* print out the server data so we know which connection to
   1.413 +	 * talk to when sending a push request */
   1.414 +	snprintf (server, sizeof (server) - 1, "%s:%hu",
   1.415 +	          net_ip_str (node->ip), node->gt_port);
   1.416 +
   1.417 +	if (is_local)
   1.418 +	{
   1.419 +		/* use the Client GUID for the user if the remote connection is
   1.420 +		 * on the Internet and the host is 0 or local */
   1.421 +		host_str = stringf_dup ("%s@%s", net_ip_str (host),
   1.422 +		                        gt_guid_str (client_guid));
   1.423 +	}
   1.424 +	else
   1.425 +	{
   1.426 +		/* Just use a plain host for cleanliness */
   1.427 +		host_str = stringf_dup ("%s", net_ip_str (host));
   1.428 +	}
   1.429 +
   1.430 +	GT->search_result (GT, search->event, host_str, server,
   1.431 +	                   url, availability, file);
   1.432 +
   1.433 +	/* update statistics */
   1.434 +	search->results++;
   1.435 +	time (&search->last_result);
   1.436 +
   1.437 +	free (host_str);
   1.438 +	free (url);
   1.439 +}
   1.440 +
   1.441 +/******************************************************************************/
   1.442 +
   1.443 +static uint8_t get_search_ttl (GtNode *node, gt_search_type_t type)
   1.444 +{
   1.445 +	char     *max_ttl;
   1.446 +	uint8_t   ttl     = 0;
   1.447 +
   1.448 +	if ((max_ttl = dataset_lookupstr (node->hdr, "x-max-ttl")))
   1.449 +		ttl = ATOI (max_ttl);
   1.450 +
   1.451 +	if (ttl > GT_SEARCH_TTL || ttl == 0)
   1.452 +		ttl = GT_SEARCH_TTL;
   1.453 +
   1.454 +	/* ok because locates are rate-limited */
   1.455 +#if 0
   1.456 +	if (type == GT_SEARCH_HASH)
   1.457 +		ttl = 1;
   1.458 +#endif
   1.459 +
   1.460 +	return ttl;
   1.461 +}
   1.462 +
   1.463 +static TCPC *broadcast_search (TCPC *c, GtNode *node, GtSearch *search)
   1.464 +{
   1.465 +	gt_query_flags_t flags;
   1.466 +	uint8_t          ttl;
   1.467 +	char            *hash = NULL;
   1.468 +	GtPacket        *pkt;
   1.469 +
   1.470 +	/* set this query as having flags to be interpolated */
   1.471 +	flags = QF_HAS_FLAGS;
   1.472 +
   1.473 +	/* request that only non-firewalled nodes respond if we are firewalled
   1.474 +	 * NOTE: if we ever support a download proxy, need to unset this */
   1.475 +	if (GT_SELF->firewalled)
   1.476 +		flags |= QF_ONLY_NON_FW;
   1.477 +
   1.478 +#ifdef USE_LIBXML2
   1.479 +	flags |= QF_WANTS_XML;
   1.480 +#endif /* USE_LIBXML2 */
   1.481 +
   1.482 +	ttl = get_search_ttl (node, search->type);
   1.483 +
   1.484 +	if (search->type == GT_SEARCH_HASH && !search->hash)
   1.485 +	{
   1.486 +		GT->DBGFN (GT, "trying to search for \"%s\" without a hash?!?",
   1.487 +		           search->query);
   1.488 +		return NULL;
   1.489 +	}
   1.490 +
   1.491 +	if (!(pkt = gt_packet_new (GT_MSG_QUERY, ttl, search->guid)))
   1.492 +		return NULL;
   1.493 +
   1.494 +	gt_packet_put_uint16 (pkt, flags);
   1.495 +	gt_packet_put_str    (pkt, search->query);
   1.496 +
   1.497 +	if (search->hash)
   1.498 +		hash = stringf_dup ("urn:sha1:%s", search->hash);
   1.499 +
   1.500 +	if (hash)
   1.501 +		gt_packet_put_str (pkt, hash);
   1.502 +
   1.503 +	gt_packet_send (c, pkt);
   1.504 +	gt_packet_free (pkt);
   1.505 +
   1.506 +	free (hash);
   1.507 +
   1.508 +	/* TODO: check error return from gt_packet_send_fmt! */
   1.509 +	search->submitted++;
   1.510 +	time (&search->last_submit);
   1.511 +
   1.512 +	return NULL;
   1.513 +}
   1.514 +
   1.515 +static BOOL submit_search (GtSearch *search, TCPC *c)
   1.516 +{
   1.517 +	if (search->results >= RESULTS_BACKOFF)
   1.518 +	{
   1.519 +		/* still count the search as submitted to this node */
   1.520 +		search->submitted++;
   1.521 +		return FALSE;
   1.522 +	}
   1.523 +
   1.524 +	broadcast_search (c, GT_NODE(c), search);
   1.525 +	return FALSE;
   1.526 +}
   1.527 +
   1.528 +static BOOL submit_searches (TCPC *c)
   1.529 +{
   1.530 +	list_foreach (active_searches, (ListForeachFunc)submit_search, c);
   1.531 +	GT_NODE(c)->search_timer = 0;
   1.532 +	return FALSE;
   1.533 +}
   1.534 +
   1.535 +static BOOL reset_submit (GtSearch *search, time_t *now)
   1.536 +{
   1.537 +	if (search->results >= RESULTS_BACKOFF)
   1.538 +		return FALSE;
   1.539 +
   1.540 +	search->last_submit = *now;
   1.541 +	return FALSE;
   1.542 +}
   1.543 +
   1.544 +void gt_searches_submit (TCPC *c, time_t delay_ms)
   1.545 +{
   1.546 +	time_t now;
   1.547 +
   1.548 +	/* reset each search timeout because we will submit each search soon */
   1.549 +	time (&now);
   1.550 +	list_foreach (active_searches, (ListForeachFunc)reset_submit, &now);
   1.551 +
   1.552 +	/* submit the searches once after a delay */
   1.553 +	if (!GT_NODE(c)->search_timer)
   1.554 +	{
   1.555 +		GT_NODE(c)->search_timer = timer_add (delay_ms,
   1.556 +		                                   (TimerCallback)submit_searches, c);
   1.557 +	}
   1.558 +}
   1.559 +
   1.560 +BOOL gnutella_search (Protocol *p, IFEvent *event, char *query, char *exclude,
   1.561 +                      char *realm, Dataset *meta)
   1.562 +{
   1.563 +	GtSearch *search;
   1.564 +
   1.565 +	search = gt_search_new (event, query, GT_SEARCH_KEYWORD);
   1.566 +	search->realm = STRDUP (realm);
   1.567 +
   1.568 +	gt_conn_foreach (GT_CONN_FOREACH(broadcast_search), search,
   1.569 +	                 GT_NODE_NONE, GT_NODE_CONNECTED, 0);
   1.570 +
   1.571 +	return TRUE;
   1.572 +}
   1.573 +
   1.574 +/*****************************************************************************/
   1.575 +
   1.576 +/*
   1.577 + * Using the hash, grab words to stuff in the query section by looking at the
   1.578 + * download list.
   1.579 + */
   1.580 +char *get_query_words (char *htype, char *hash)
   1.581 +{
   1.582 +	Source   *src;
   1.583 +	GtSource *gt_src;
   1.584 +	char     *dup;
   1.585 +
   1.586 +	if (htype && strcmp (htype, "SHA1") != 0)
   1.587 +	{
   1.588 +		GT->DBGFN (GT, "htype != \"SHA1\"!?: %s", htype);
   1.589 +		return NULL;
   1.590 +	}
   1.591 +
   1.592 +	/* HACK: need gift's prefix */
   1.593 +	if (!(dup = stringf_dup ("SHA1:%s", hash)))
   1.594 +		return NULL;
   1.595 +
   1.596 +	src = gt_download_lookup (dup);
   1.597 +	free (dup);
   1.598 +
   1.599 +	if (!src)
   1.600 +		return NULL;
   1.601 +
   1.602 +	if (!(gt_src = src->udata))
   1.603 +	{
   1.604 +		GT->DBGFN (GT, "gt_src == NULL?!?!");
   1.605 +		return NULL;
   1.606 +	}
   1.607 +
   1.608 +	return gt_url_decode (gt_src->filename);
   1.609 +}
   1.610 +
   1.611 +/*
   1.612 + * Returns TRUE if the current locate is ok to send and FALSE if it should be
   1.613 + * dropped to rate-limit locates.  To determine that, we assign the locate a
   1.614 + * "probability of passage".  Then we roll dice and if it's less than the
   1.615 + * probability, accept.
   1.616 + *
   1.617 + * For each locate attempt the probability of success for the next locate is
   1.618 + * halved, down to a minimum of 0.01%.  For each minute that passes since the
   1.619 + * last locate, the probability of the locate succeeding increases by 1%.
   1.620 + */
   1.621 +static BOOL should_send_locate (void)
   1.622 +{
   1.623 +	static time_t last_locate = 0;
   1.624 +	time_t        now;
   1.625 +	double        n;
   1.626 +	BOOL          passed;
   1.627 +
   1.628 +	time (&now);
   1.629 +
   1.630 +	if (last_locate == 0)
   1.631 +		locate_pass_prob = 100.0;
   1.632 +	else
   1.633 +		locate_pass_prob += difftime (now, last_locate) / (1.0 * EMINUTES);
   1.634 +
   1.635 +	last_locate = now;
   1.636 +
   1.637 +	if (locate_pass_prob > 100.0)
   1.638 +		locate_pass_prob = 100.0;
   1.639 +
   1.640 +	/* hmm, should this be removed? */
   1.641 +	if (locate_pass_prob < 0.01)
   1.642 +		locate_pass_prob = 0.01;
   1.643 +
   1.644 +	n = 100.0 * rand() / (RAND_MAX + 1.0);
   1.645 +
   1.646 +	GT->DBGFN (GT, "locate_pass_prob=%f n=%f", locate_pass_prob, n);
   1.647 +	passed = BOOL_EXPR (n < locate_pass_prob);
   1.648 +
   1.649 +	/* drop next chance of succeeding */
   1.650 +	locate_pass_prob /= 2;
   1.651 +
   1.652 +	return passed;
   1.653 +}
   1.654 +
   1.655 +BOOL gnutella_locate (Protocol *p, IFEvent *event, char *htype, char *hash)
   1.656 +{
   1.657 +	GtSearch      *search;
   1.658 +	unsigned char *bin;
   1.659 +	char          *fname;
   1.660 +
   1.661 +	/* Only locate hashes which are valid on Gnutella. */
   1.662 +	if (STRCMP (htype, "SHA1"))
   1.663 +		return FALSE;
   1.664 +
   1.665 +	GT->DBGFN (GT, "new hash search: %s", hash);
   1.666 +
   1.667 +	/* sha1_bin() needs a string of at least 32 characters */
   1.668 +	if (STRLEN (hash) < 32)
   1.669 +		return FALSE;
   1.670 +
   1.671 +	/* skip the hash if it's not parseable in base32 */
   1.672 +	if (!(bin = sha1_bin (hash)))
   1.673 +		return FALSE;
   1.674 +
   1.675 +	free (bin);
   1.676 +
   1.677 +	/* rate-limit locate searches to save bandwidth */
   1.678 +	if (should_send_locate () == FALSE)
   1.679 +	{
   1.680 +		GT->DBGFN (GT, "dropping locate for %s "
   1.681 +		           "(too many searches in short period)", hash);
   1.682 +		return FALSE;
   1.683 +	}
   1.684 +
   1.685 +	/* make sure the hash is uppercase (canonical form on Gnet) */
   1.686 +	string_upper (hash);
   1.687 +
   1.688 +	/*
   1.689 +	 * Look for a download with this hash, to put those words in the query to
   1.690 +	 * reduce the bandwidth consumed through QRP.
   1.691 +	 */
   1.692 +	if (!(fname = get_query_words (htype, hash)))
   1.693 +		fname = STRDUP ("");
   1.694 +
   1.695 +	if (!(search = gt_search_new (event, fname, GT_SEARCH_HASH)))
   1.696 +	{
   1.697 +		free (fname);
   1.698 +		return FALSE;
   1.699 +	}
   1.700 +
   1.701 +	free (fname);
   1.702 +
   1.703 +	search->hash = STRDUP (hash);
   1.704 +
   1.705 +	gt_conn_foreach (GT_CONN_FOREACH(broadcast_search), search, GT_NODE_NONE,
   1.706 +	                 GT_NODE_CONNECTED, 0);
   1.707 +
   1.708 +	return TRUE;
   1.709 +}
   1.710 +
   1.711 +void gnutella_search_cancel (Protocol *p, IFEvent *event)
   1.712 +{
   1.713 +	gt_search_disable (event);
   1.714 +}
   1.715 +
   1.716 +/*****************************************************************************/
   1.717 +
   1.718 +void gt_search_init (void)
   1.719 +{
   1.720 +	/* nothing */
   1.721 +}
   1.722 +
   1.723 +BOOL rm_search (GtSearch *search, void *udata)
   1.724 +{
   1.725 +	gt_search_free (search);
   1.726 +
   1.727 +	/* return FALSE here because gt_search_free() removes search from list */
   1.728 +	return FALSE;
   1.729 +}
   1.730 +
   1.731 +void gt_search_cleanup (void)
   1.732 +{
   1.733 +	list_foreach_remove (active_searches, (ListForeachFunc)rm_search, NULL);
   1.734 +	assert (active_searches == NULL);
   1.735 +}