1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/gt_node_list.c	Sat Feb 20 21:18:28 2010 -0800
     1.3 @@ -0,0 +1,567 @@
     1.4 +/*
     1.5 + * $Id: gt_node_list.c,v 1.12 2004/01/29 07:50:25 hipnod 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 +
    1.25 +/*
    1.26 + * TODO: rename gt_conn -> gt_node_list
    1.27 + */
    1.28 +
    1.29 +/*****************************************************************************/
    1.30 +
    1.31 +/* list of all nodes -- NOTE: duplicated info in gt_node.c */
    1.32 +static List      *node_list;
    1.33 +
    1.34 +/* last place in node_list for gt_conn_foreach */
    1.35 +static List      *iterator;
    1.36 +
    1.37 +/* cache of length of connected portion of node list by class (GtNodeLeaf,
    1.38 + * first, then GtNodeUltra) */
    1.39 +static int        len_cache[2] = { 0 };
    1.40 +
    1.41 +/*****************************************************************************/
    1.42 +
    1.43 +static void move_iterator (GtNode *mv)
    1.44 +{
    1.45 +	if (list_nth_data (iterator, 0) == mv)
    1.46 +		iterator = list_next (iterator);
    1.47 +}
    1.48 +
    1.49 +void gt_conn_add (GtNode *node)
    1.50 +{
    1.51 +	if (!node)
    1.52 +	{
    1.53 +		GIFT_ERROR (("adding null node to node list"));
    1.54 +		return;
    1.55 +	}
    1.56 +
    1.57 +	node_list = list_append (node_list, node);
    1.58 +}
    1.59 +
    1.60 +void gt_conn_remove (GtNode *node)
    1.61 +{
    1.62 +	if (!list_find (node_list, node))
    1.63 +		return;
    1.64 +
    1.65 +	/* move the iterator if it's pointing at the node we're removing */
    1.66 +	move_iterator (node);
    1.67 +
    1.68 +	node_list = list_remove (node_list, node);
    1.69 +}
    1.70 +
    1.71 +static void trace_list (List *nodes)
    1.72 +{
    1.73 +	GtNode *node;
    1.74 +
    1.75 +	if (!nodes)
    1.76 +		return;
    1.77 +
    1.78 +	node = list_nth_data (nodes, 0);
    1.79 +
    1.80 +	assert (node != NULL);
    1.81 +	assert (GT_CONN(node) != NULL);
    1.82 +
    1.83 +	GT->DBGFN (GT, "%s:%hu", net_ip_str (node->ip), node->gt_port);
    1.84 +
    1.85 +	if (list_next (nodes))
    1.86 +		trace_list (list_next (nodes));
    1.87 +}
    1.88 +
    1.89 +/*****************************************************************************/
    1.90 +
    1.91 +GtNode *gt_conn_foreach (GtConnForeachFunc func, void *udata,
    1.92 +                         gt_node_class_t klass, gt_node_state_t state,
    1.93 +                         int iter)
    1.94 +{
    1.95 +	GtNode      *node;
    1.96 +	TCPC        *c;
    1.97 +	GtNode      *ret       = NULL;
    1.98 +	List        *ptr;
    1.99 +	List        *start;
   1.100 +	List        *next;
   1.101 +	unsigned int i, count;
   1.102 +	int          looped    = FALSE;
   1.103 +	int          iterating = FALSE;
   1.104 +
   1.105 +	assert (func != NULL);
   1.106 +
   1.107 +#if 0
   1.108 +	GT->DBGFN (GT, "length of conn list: %u", list_length (connections));
   1.109 +#endif
   1.110 +
   1.111 +	if (iter)
   1.112 +		iterating = TRUE;
   1.113 +
   1.114 +	if (!iterator)
   1.115 +		iterator = node_list;
   1.116 +
   1.117 +	start = ptr = (iterating) ? iterator : node_list;
   1.118 +
   1.119 +	/* having count be the static list length should keep
   1.120 +	 * concurrent conn_adds from making us never stop */
   1.121 +	count = list_length (node_list);
   1.122 +
   1.123 +	/* hack for backward-compatible interface */
   1.124 +	if (state == (gt_node_state_t) -1)
   1.125 +		state = GT_NODE_ANY;
   1.126 +
   1.127 +	for (i = 0; i < count; i++)
   1.128 +	{
   1.129 +		if (iter && !ptr && !looped)
   1.130 +		{
   1.131 +			/* data only gets appended to connection list:
   1.132 +			 * safe to use head of connection list (connections) */
   1.133 +			ptr = node_list;
   1.134 +			looped = TRUE;
   1.135 +		}
   1.136 +
   1.137 +		if (!ptr)
   1.138 +			break;
   1.139 +
   1.140 +		/* we wrapped to the beginning, but have just reached the original
   1.141 +		 * start so we should bail out */
   1.142 +		if (looped && ptr == start)
   1.143 +			break;
   1.144 +
   1.145 +		node = ptr->data;
   1.146 +		c = GT_CONN(node);
   1.147 +
   1.148 +		assert (node != NULL);
   1.149 +
   1.150 +		if (klass && !(node->klass & klass))
   1.151 +		{
   1.152 +			ptr = list_next (ptr);
   1.153 +			continue;
   1.154 +		}
   1.155 +
   1.156 +		if (state != GT_NODE_ANY && node->state != state)
   1.157 +		{
   1.158 +			ptr = list_next (ptr);
   1.159 +			continue;
   1.160 +		}
   1.161 +
   1.162 +		/* grab the next item. this allows the callback to free this item */
   1.163 +		next = list_next (ptr);
   1.164 +
   1.165 +		ret = (*func) (c, node, udata);
   1.166 +
   1.167 +		ptr = next;
   1.168 +
   1.169 +		if (ret)
   1.170 +			break;
   1.171 +
   1.172 +		if (iterating && --iter == 0)
   1.173 +			break;
   1.174 +	}
   1.175 +
   1.176 +	/* save the position for next time */
   1.177 +	if (iterating)
   1.178 +		iterator = ptr;
   1.179 +
   1.180 +	return ret;
   1.181 +}
   1.182 +
   1.183 +/*****************************************************************************/
   1.184 +
   1.185 +static void add_connected (gt_node_class_t klass)
   1.186 +{
   1.187 +	int add;
   1.188 +
   1.189 +	if (klass != GT_NODE_LEAF && klass != GT_NODE_ULTRA)
   1.190 +		return;
   1.191 +
   1.192 +	add = (klass == GT_NODE_LEAF ? 0 : 1);
   1.193 +	len_cache[add]++;
   1.194 +}
   1.195 +
   1.196 +static void del_connected (gt_node_class_t klass)
   1.197 +{
   1.198 +	int del;
   1.199 +
   1.200 +	if (klass != GT_NODE_LEAF && klass != GT_NODE_ULTRA)
   1.201 +		return;
   1.202 +
   1.203 +	del = (klass == GT_NODE_LEAF ? 0 : 1);
   1.204 +	len_cache[del]--;
   1.205 +}
   1.206 +
   1.207 +void gt_conn_set_state (GtNode *node, gt_node_state_t old_state,
   1.208 +                        gt_node_state_t new_state)
   1.209 +{
   1.210 +	if (new_state == GT_NODE_CONNECTED && old_state != GT_NODE_CONNECTED)
   1.211 +		add_connected (node->klass);
   1.212 +
   1.213 +	if (new_state != GT_NODE_CONNECTED && old_state == GT_NODE_CONNECTED)
   1.214 +		del_connected (node->klass);
   1.215 +}
   1.216 +
   1.217 +void gt_conn_set_class (GtNode *node, gt_node_class_t old_class,
   1.218 +                        gt_node_class_t new_class)
   1.219 +{
   1.220 +	if (node->state != GT_NODE_CONNECTED)
   1.221 +		return;
   1.222 +
   1.223 +	del_connected (old_class);
   1.224 +	add_connected (new_class);
   1.225 +
   1.226 +	assert (len_cache[0] >= 0);
   1.227 +	assert (len_cache[1] >= 0);
   1.228 +}
   1.229 +
   1.230 +static int check_len_cache (gt_node_class_t klass)
   1.231 +{
   1.232 +	int len = 0;
   1.233 +
   1.234 +	if (klass == GT_NODE_NONE)
   1.235 +		klass = GT_NODE_LEAF | GT_NODE_ULTRA;
   1.236 +
   1.237 +	if (klass & GT_NODE_LEAF)
   1.238 +		len += len_cache[0];
   1.239 +
   1.240 +	if (klass & GT_NODE_ULTRA)
   1.241 +		len += len_cache[1];
   1.242 +
   1.243 +	return len;
   1.244 +}
   1.245 +
   1.246 +static GtNode *conn_counter (TCPC *c, GtNode *node, int *length)
   1.247 +{
   1.248 +	(*length)++;
   1.249 +	return NULL;
   1.250 +}
   1.251 +
   1.252 +int gt_conn_length (gt_node_class_t klass, gt_node_state_t state)
   1.253 +{
   1.254 +	int ret = 0;
   1.255 +	int cached_len;
   1.256 +
   1.257 +	/*
   1.258 +	 * We keep a small cache of the length of connected ultrapeers+leaves
   1.259 +	 * so we don't have to traverse the list most of the time here.
   1.260 +	 *
   1.261 +	 * Traversal still happens now as a sanity check.
   1.262 +	 */
   1.263 +	if (state == GT_NODE_CONNECTED &&
   1.264 +	    (klass == GT_NODE_NONE || klass == GT_NODE_LEAF ||
   1.265 +		 klass == GT_NODE_ULTRA))
   1.266 +	{
   1.267 +		cached_len = check_len_cache (klass);
   1.268 +
   1.269 +		/* make sure the cache length is the same as the real one */
   1.270 +		gt_conn_foreach (GT_CONN_FOREACH(conn_counter), &ret, klass, state, 0);
   1.271 +		assert (ret == cached_len);
   1.272 +
   1.273 +		return cached_len;
   1.274 +	}
   1.275 +
   1.276 +	gt_conn_foreach (GT_CONN_FOREACH(conn_counter), &ret,
   1.277 +	                 klass, state, 0);
   1.278 +
   1.279 +	return ret;
   1.280 +}
   1.281 +
   1.282 +/*****************************************************************************/
   1.283 +
   1.284 +static GtNode *select_rand (TCPC *c, GtNode *node, void **cmp)
   1.285 +{
   1.286 +	int     *nr    = cmp[0];
   1.287 +	GtNode **ret   = cmp[1];
   1.288 +	float    range = *nr;
   1.289 +	float    prob;
   1.290 +
   1.291 +	/* make sure we pick at least one */
   1.292 +	if (!*ret)
   1.293 +		*ret = node;
   1.294 +
   1.295 +	/* set the probability of selecting this node */
   1.296 +	prob = range * rand() / (RAND_MAX + 1.0);
   1.297 +
   1.298 +	if (prob < 1)
   1.299 +		*ret = node;
   1.300 +
   1.301 +	(*nr)++;
   1.302 +
   1.303 +	/* we dont use the return value here, because we need to try
   1.304 +	 * all the nodes, and returning non-null here short-circuits */
   1.305 +	return NULL;
   1.306 +}
   1.307 +
   1.308 +/*
   1.309 + * Pick a node at random that is also of the specified 
   1.310 + * class and state.
   1.311 + */
   1.312 +GtNode *gt_conn_random (gt_node_class_t klass, gt_node_state_t state)
   1.313 +{
   1.314 +	void   *cmp[2];
   1.315 +	int     nr;   
   1.316 +	GtNode *ret = NULL;
   1.317 +
   1.318 +	/* initial probability */
   1.319 +	nr = 1;
   1.320 +
   1.321 +	cmp[0] = &nr;
   1.322 +	cmp[1] = &ret;
   1.323 +
   1.324 +	gt_conn_foreach (GT_CONN_FOREACH(select_rand), cmp,
   1.325 +	                 klass, state, 0);
   1.326 +
   1.327 +	return ret;
   1.328 +}
   1.329 +
   1.330 +/*****************************************************************************/
   1.331 +
   1.332 +static BOOL collect_old (GtNode *node, void **data)
   1.333 +{
   1.334 +	List   **to_free    = data[0];
   1.335 +	int     *max_tofree = data[1];
   1.336 +
   1.337 +	/* don't make the node list too small */
   1.338 +	if (*max_tofree == 0)
   1.339 +		return FALSE;
   1.340 +
   1.341 +	if (gt_node_freeable (node))
   1.342 +	{
   1.343 +		/* protect the iterator because we're removing a node */
   1.344 +		move_iterator (node);
   1.345 +
   1.346 +		(*max_tofree)--;
   1.347 +		*to_free = list_append (*to_free, node);
   1.348 +
   1.349 +		return TRUE;
   1.350 +	}
   1.351 +
   1.352 +	return FALSE;
   1.353 +}
   1.354 +
   1.355 +static BOOL dump_node (GtNode *node, void *udata)
   1.356 +{
   1.357 +	gt_node_free (node);
   1.358 +	return TRUE;
   1.359 +}
   1.360 +
   1.361 +/*
   1.362 + * NOTE: We can't re-descend the node_list by calling gt_node_free [which
   1.363 + * calls gt_conn_remove->list_remove] while iterating the node_list in
   1.364 + * list_foreach_remove. So, we build a second a list of nodes to free while
   1.365 + * removing those from node_list "by hand" and then free that list.
   1.366 + */
   1.367 +void gt_conn_trim (void)
   1.368 +{
   1.369 +	List   *to_free     = NULL;
   1.370 +	int     max_tofree;
   1.371 +	int     len;
   1.372 +	void   *data[2];
   1.373 +
   1.374 +	len = list_length (node_list);
   1.375 +	max_tofree = MAX (0, len - 500);
   1.376 +
   1.377 +	data[0] = &to_free;
   1.378 +	data[1] = &max_tofree;
   1.379 +
   1.380 +	/* get rid of the oldest nodes first */
   1.381 +	gt_conn_sort ((CompareFunc)gt_conn_sort_vit_neg);
   1.382 +
   1.383 +	node_list = list_foreach_remove (node_list, (ListForeachFunc)collect_old,
   1.384 +	                                 data);
   1.385 +
   1.386 +	GT->DBGFN (GT, "trimming %d/%d nodes", list_length (to_free), len);
   1.387 +	list_foreach_remove (to_free, (ListForeachFunc)dump_node, NULL);
   1.388 +
   1.389 +	/* set the node list back to rights wrt vitality */
   1.390 +	gt_conn_sort ((CompareFunc)gt_conn_sort_vit);
   1.391 +
   1.392 +	/* reset the iterator to some random node */
   1.393 +	iterator = list_nth (node_list,
   1.394 +	                     (float)rand() * len / (RAND_MAX + 1.0));
   1.395 +}
   1.396 +
   1.397 +/*****************************************************************************/
   1.398 +
   1.399 +int gt_conn_sort_vit (GtNode *a, GtNode *b)
   1.400 +{
   1.401 +	if (a->vitality > b->vitality)
   1.402 +		return -1;
   1.403 +	else if (a->vitality < b->vitality)
   1.404 +		return 1;
   1.405 +	else
   1.406 +		return 0;
   1.407 +}
   1.408 +
   1.409 +int gt_conn_sort_vit_neg (GtNode *a, GtNode *b)
   1.410 +{
   1.411 +	return -gt_conn_sort_vit (a, b);
   1.412 +}
   1.413 +
   1.414 +/* NOTE: this isnt safe to call at all times */
   1.415 +void gt_conn_sort (CompareFunc func)
   1.416 +{
   1.417 +	node_list = list_sort (node_list, func);
   1.418 +
   1.419 +	/* reset the iterator */
   1.420 +	iterator = NULL;
   1.421 +}
   1.422 +
   1.423 +/*****************************************************************************/
   1.424 +
   1.425 +struct _sync_args
   1.426 +{
   1.427 +	time_t tm;
   1.428 +	FILE  *f;
   1.429 +};
   1.430 +
   1.431 +static GtNode *sync_node (TCPC *c, GtNode *node, struct _sync_args *sync)
   1.432 +{
   1.433 +	size_t ret;
   1.434 +
   1.435 +	/* node->vitality is updated lazily, to avoid a syscall for every
   1.436 +	 * packet.  Maybe this isnt worth it */
   1.437 +	if (node->state & GT_NODE_CONNECTED)
   1.438 +		node->vitality = sync->tm;
   1.439 +
   1.440 +	/* only cache the node if we have connected to it before successfully */
   1.441 +	if (node->vitality > 0 &&
   1.442 +	    node->gt_port > 0)
   1.443 +	{
   1.444 +		ret = fprintf (sync->f, "%lu %s:%hu %lu %lu\n", (long)node->vitality,
   1.445 +		               net_ip_str (node->ip), node->gt_port,
   1.446 +		               (long)node->size_kb, (long)node->files);
   1.447 +
   1.448 +		/* stop iterating if there was an error */
   1.449 +		if (ret <= 0)
   1.450 +			return node;
   1.451 +	}
   1.452 +
   1.453 +	return NULL;
   1.454 +}
   1.455 +
   1.456 +void gt_node_list_save (void)
   1.457 +{
   1.458 +	struct _sync_args sync;
   1.459 +	char  *tmp_path;
   1.460 +
   1.461 +	time (&sync.tm);
   1.462 +	tmp_path = STRDUP (gift_conf_path ("Gnutella/nodes.tmp"));
   1.463 +
   1.464 +	if (!(sync.f = fopen (gift_conf_path ("Gnutella/nodes.tmp"), "w")))
   1.465 +	{
   1.466 +		GT->DBGFN (GT, "error opening tmp file: %s", GIFT_STRERROR ());
   1.467 +		free (tmp_path);
   1.468 +		return;
   1.469 +	}
   1.470 +
   1.471 +	/*
   1.472 +	 * The nodes file is fairly important. Check for errors when writing to
   1.473 +	 * the disk.
   1.474 +	 */
   1.475 +	if (gt_conn_foreach (GT_CONN_FOREACH(sync_node), &sync,
   1.476 +	                     GT_NODE_NONE, GT_NODE_ANY, 0) != NULL)
   1.477 +	{
   1.478 +		GT->warn (GT, "error writing nodes file: %s", GIFT_STRERROR());
   1.479 +		fclose (sync.f);
   1.480 +		free (tmp_path);
   1.481 +		return;
   1.482 +	}
   1.483 +
   1.484 +	if (fclose (sync.f) != 0)
   1.485 +	{
   1.486 +		GT->warn (GT, "error closing nodes file: %s", GIFT_STRERROR());
   1.487 +		free (tmp_path);
   1.488 +		return;
   1.489 +	}
   1.490 +
   1.491 +	file_mv (tmp_path, gift_conf_path ("Gnutella/nodes"));
   1.492 +
   1.493 +	free (tmp_path);
   1.494 +}
   1.495 +
   1.496 +static void load_nodes (/*const*/ char *conf_path, gt_node_class_t klass)
   1.497 +{
   1.498 +	GtNode *node;
   1.499 +	FILE   *f;
   1.500 +	char   *buf = NULL;
   1.501 +	char   *ptr;
   1.502 +
   1.503 +	f = fopen (gift_conf_path (conf_path), "r");
   1.504 +
   1.505 +	/* try the global nodes file */
   1.506 +	if (!f)
   1.507 +	{
   1.508 +		char *filename;
   1.509 +
   1.510 +		if (!(filename = malloc (strlen (platform_data_dir ()) + 50)))
   1.511 +			return;
   1.512 +
   1.513 +		sprintf (filename, "%s/%s", platform_data_dir (), conf_path);
   1.514 +
   1.515 +		f = fopen (filename, "r");
   1.516 +
   1.517 +		free (filename);
   1.518 +	}
   1.519 +
   1.520 +	if (!f)
   1.521 +		return;
   1.522 +
   1.523 +	while (file_read_line (f, &buf))
   1.524 +	{
   1.525 +		unsigned long  vitality;
   1.526 +		in_addr_t      ip;
   1.527 +		in_port_t      port;
   1.528 +		uint32_t       size_kb;
   1.529 +		uint32_t       files;
   1.530 +
   1.531 +		ptr = buf;
   1.532 +
   1.533 +		/* [vitality] [ip]:[port] [shares size(kB)] [file count] */
   1.534 +
   1.535 +		vitality = ATOUL  (string_sep (&ptr, " "));
   1.536 +		ip       = net_ip (string_sep (&ptr, ":"));
   1.537 +		port     = ATOI   (string_sep (&ptr, " "));
   1.538 +		size_kb  = ATOI   (string_sep (&ptr, " "));
   1.539 +		files    = ATOI   (string_sep (&ptr, " "));
   1.540 +
   1.541 +		if (!ip || ip == INADDR_NONE)
   1.542 +			continue;
   1.543 +
   1.544 +		if (size_kb == (uint32_t)-1)
   1.545 +			size_kb = 0;
   1.546 +
   1.547 +		if (files == (uint32_t)-1)
   1.548 +			files = 0;
   1.549 +
   1.550 +		node = gt_node_register (ip, port, klass);
   1.551 +
   1.552 +		if (!node)
   1.553 +			continue;
   1.554 +
   1.555 +		node->vitality = vitality;
   1.556 +
   1.557 +		node->size_kb  = size_kb;
   1.558 +		node->files    = files;
   1.559 +	}
   1.560 +
   1.561 +	fclose (f);
   1.562 +}
   1.563 +
   1.564 +void gt_node_list_load (void)
   1.565 +{
   1.566 +	load_nodes ("Gnutella/nodes", GT_NODE_ULTRA);
   1.567 +
   1.568 +	/* sort the list so we contact the most recent nodes first */
   1.569 +	gt_conn_sort ((CompareFunc) gt_conn_sort_vit);
   1.570 +}