paulo@0: /*
paulo@0:  * $Id: gt_node_list.c,v 1.12 2004/01/29 07:50:25 hipnod Exp $
paulo@0:  *
paulo@0:  * Copyright (C) 2001-2003 giFT project (gift.sourceforge.net)
paulo@0:  *
paulo@0:  * This program is free software; you can redistribute it and/or modify it
paulo@0:  * under the terms of the GNU General Public License as published by the
paulo@0:  * Free Software Foundation; either version 2, or (at your option) any
paulo@0:  * later version.
paulo@0:  *
paulo@0:  * This program is distributed in the hope that it will be useful, but
paulo@0:  * WITHOUT ANY WARRANTY; without even the implied warranty of
paulo@0:  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
paulo@0:  * General Public License for more details.
paulo@0:  */
paulo@0: 
paulo@0: #include "gt_gnutella.h"
paulo@0: 
paulo@0: #include "gt_node.h"
paulo@0: #include "gt_node_list.h"
paulo@0: 
paulo@0: /*
paulo@0:  * TODO: rename gt_conn -> gt_node_list
paulo@0:  */
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: /* list of all nodes -- NOTE: duplicated info in gt_node.c */
paulo@0: static List      *node_list;
paulo@0: 
paulo@0: /* last place in node_list for gt_conn_foreach */
paulo@0: static List      *iterator;
paulo@0: 
paulo@0: /* cache of length of connected portion of node list by class (GtNodeLeaf,
paulo@0:  * first, then GtNodeUltra) */
paulo@0: static int        len_cache[2] = { 0 };
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: static void move_iterator (GtNode *mv)
paulo@0: {
paulo@0: 	if (list_nth_data (iterator, 0) == mv)
paulo@0: 		iterator = list_next (iterator);
paulo@0: }
paulo@0: 
paulo@0: void gt_conn_add (GtNode *node)
paulo@0: {
paulo@0: 	if (!node)
paulo@0: 	{
paulo@0: 		GIFT_ERROR (("adding null node to node list"));
paulo@0: 		return;
paulo@0: 	}
paulo@0: 
paulo@0: 	node_list = list_append (node_list, node);
paulo@0: }
paulo@0: 
paulo@0: void gt_conn_remove (GtNode *node)
paulo@0: {
paulo@0: 	if (!list_find (node_list, node))
paulo@0: 		return;
paulo@0: 
paulo@0: 	/* move the iterator if it's pointing at the node we're removing */
paulo@0: 	move_iterator (node);
paulo@0: 
paulo@0: 	node_list = list_remove (node_list, node);
paulo@0: }
paulo@0: 
paulo@0: static void trace_list (List *nodes)
paulo@0: {
paulo@0: 	GtNode *node;
paulo@0: 
paulo@0: 	if (!nodes)
paulo@0: 		return;
paulo@0: 
paulo@0: 	node = list_nth_data (nodes, 0);
paulo@0: 
paulo@0: 	assert (node != NULL);
paulo@0: 	assert (GT_CONN(node) != NULL);
paulo@0: 
paulo@0: 	GT->DBGFN (GT, "%s:%hu", net_ip_str (node->ip), node->gt_port);
paulo@0: 
paulo@0: 	if (list_next (nodes))
paulo@0: 		trace_list (list_next (nodes));
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: GtNode *gt_conn_foreach (GtConnForeachFunc func, void *udata,
paulo@0:                          gt_node_class_t klass, gt_node_state_t state,
paulo@0:                          int iter)
paulo@0: {
paulo@0: 	GtNode      *node;
paulo@0: 	TCPC        *c;
paulo@0: 	GtNode      *ret       = NULL;
paulo@0: 	List        *ptr;
paulo@0: 	List        *start;
paulo@0: 	List        *next;
paulo@0: 	unsigned int i, count;
paulo@0: 	int          looped    = FALSE;
paulo@0: 	int          iterating = FALSE;
paulo@0: 
paulo@0: 	assert (func != NULL);
paulo@0: 
paulo@0: #if 0
paulo@0: 	GT->DBGFN (GT, "length of conn list: %u", list_length (connections));
paulo@0: #endif
paulo@0: 
paulo@0: 	if (iter)
paulo@0: 		iterating = TRUE;
paulo@0: 
paulo@0: 	if (!iterator)
paulo@0: 		iterator = node_list;
paulo@0: 
paulo@0: 	start = ptr = (iterating) ? iterator : node_list;
paulo@0: 
paulo@0: 	/* having count be the static list length should keep
paulo@0: 	 * concurrent conn_adds from making us never stop */
paulo@0: 	count = list_length (node_list);
paulo@0: 
paulo@0: 	/* hack for backward-compatible interface */
paulo@0: 	if (state == (gt_node_state_t) -1)
paulo@0: 		state = GT_NODE_ANY;
paulo@0: 
paulo@0: 	for (i = 0; i < count; i++)
paulo@0: 	{
paulo@0: 		if (iter && !ptr && !looped)
paulo@0: 		{
paulo@0: 			/* data only gets appended to connection list:
paulo@0: 			 * safe to use head of connection list (connections) */
paulo@0: 			ptr = node_list;
paulo@0: 			looped = TRUE;
paulo@0: 		}
paulo@0: 
paulo@0: 		if (!ptr)
paulo@0: 			break;
paulo@0: 
paulo@0: 		/* we wrapped to the beginning, but have just reached the original
paulo@0: 		 * start so we should bail out */
paulo@0: 		if (looped && ptr == start)
paulo@0: 			break;
paulo@0: 
paulo@0: 		node = ptr->data;
paulo@0: 		c = GT_CONN(node);
paulo@0: 
paulo@0: 		assert (node != NULL);
paulo@0: 
paulo@0: 		if (klass && !(node->klass & klass))
paulo@0: 		{
paulo@0: 			ptr = list_next (ptr);
paulo@0: 			continue;
paulo@0: 		}
paulo@0: 
paulo@0: 		if (state != GT_NODE_ANY && node->state != state)
paulo@0: 		{
paulo@0: 			ptr = list_next (ptr);
paulo@0: 			continue;
paulo@0: 		}
paulo@0: 
paulo@0: 		/* grab the next item. this allows the callback to free this item */
paulo@0: 		next = list_next (ptr);
paulo@0: 
paulo@0: 		ret = (*func) (c, node, udata);
paulo@0: 
paulo@0: 		ptr = next;
paulo@0: 
paulo@0: 		if (ret)
paulo@0: 			break;
paulo@0: 
paulo@0: 		if (iterating && --iter == 0)
paulo@0: 			break;
paulo@0: 	}
paulo@0: 
paulo@0: 	/* save the position for next time */
paulo@0: 	if (iterating)
paulo@0: 		iterator = ptr;
paulo@0: 
paulo@0: 	return ret;
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: static void add_connected (gt_node_class_t klass)
paulo@0: {
paulo@0: 	int add;
paulo@0: 
paulo@0: 	if (klass != GT_NODE_LEAF && klass != GT_NODE_ULTRA)
paulo@0: 		return;
paulo@0: 
paulo@0: 	add = (klass == GT_NODE_LEAF ? 0 : 1);
paulo@0: 	len_cache[add]++;
paulo@0: }
paulo@0: 
paulo@0: static void del_connected (gt_node_class_t klass)
paulo@0: {
paulo@0: 	int del;
paulo@0: 
paulo@0: 	if (klass != GT_NODE_LEAF && klass != GT_NODE_ULTRA)
paulo@0: 		return;
paulo@0: 
paulo@0: 	del = (klass == GT_NODE_LEAF ? 0 : 1);
paulo@0: 	len_cache[del]--;
paulo@0: }
paulo@0: 
paulo@0: void gt_conn_set_state (GtNode *node, gt_node_state_t old_state,
paulo@0:                         gt_node_state_t new_state)
paulo@0: {
paulo@0: 	if (new_state == GT_NODE_CONNECTED && old_state != GT_NODE_CONNECTED)
paulo@0: 		add_connected (node->klass);
paulo@0: 
paulo@0: 	if (new_state != GT_NODE_CONNECTED && old_state == GT_NODE_CONNECTED)
paulo@0: 		del_connected (node->klass);
paulo@0: }
paulo@0: 
paulo@0: void gt_conn_set_class (GtNode *node, gt_node_class_t old_class,
paulo@0:                         gt_node_class_t new_class)
paulo@0: {
paulo@0: 	if (node->state != GT_NODE_CONNECTED)
paulo@0: 		return;
paulo@0: 
paulo@0: 	del_connected (old_class);
paulo@0: 	add_connected (new_class);
paulo@0: 
paulo@0: 	assert (len_cache[0] >= 0);
paulo@0: 	assert (len_cache[1] >= 0);
paulo@0: }
paulo@0: 
paulo@0: static int check_len_cache (gt_node_class_t klass)
paulo@0: {
paulo@0: 	int len = 0;
paulo@0: 
paulo@0: 	if (klass == GT_NODE_NONE)
paulo@0: 		klass = GT_NODE_LEAF | GT_NODE_ULTRA;
paulo@0: 
paulo@0: 	if (klass & GT_NODE_LEAF)
paulo@0: 		len += len_cache[0];
paulo@0: 
paulo@0: 	if (klass & GT_NODE_ULTRA)
paulo@0: 		len += len_cache[1];
paulo@0: 
paulo@0: 	return len;
paulo@0: }
paulo@0: 
paulo@0: static GtNode *conn_counter (TCPC *c, GtNode *node, int *length)
paulo@0: {
paulo@0: 	(*length)++;
paulo@0: 	return NULL;
paulo@0: }
paulo@0: 
paulo@0: int gt_conn_length (gt_node_class_t klass, gt_node_state_t state)
paulo@0: {
paulo@0: 	int ret = 0;
paulo@0: 	int cached_len;
paulo@0: 
paulo@0: 	/*
paulo@0: 	 * We keep a small cache of the length of connected ultrapeers+leaves
paulo@0: 	 * so we don't have to traverse the list most of the time here.
paulo@0: 	 *
paulo@0: 	 * Traversal still happens now as a sanity check.
paulo@0: 	 */
paulo@0: 	if (state == GT_NODE_CONNECTED &&
paulo@0: 	    (klass == GT_NODE_NONE || klass == GT_NODE_LEAF ||
paulo@0: 		 klass == GT_NODE_ULTRA))
paulo@0: 	{
paulo@0: 		cached_len = check_len_cache (klass);
paulo@0: 
paulo@0: 		/* make sure the cache length is the same as the real one */
paulo@0: 		gt_conn_foreach (GT_CONN_FOREACH(conn_counter), &ret, klass, state, 0);
paulo@0: 		assert (ret == cached_len);
paulo@0: 
paulo@0: 		return cached_len;
paulo@0: 	}
paulo@0: 
paulo@0: 	gt_conn_foreach (GT_CONN_FOREACH(conn_counter), &ret,
paulo@0: 	                 klass, state, 0);
paulo@0: 
paulo@0: 	return ret;
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: static GtNode *select_rand (TCPC *c, GtNode *node, void **cmp)
paulo@0: {
paulo@0: 	int     *nr    = cmp[0];
paulo@0: 	GtNode **ret   = cmp[1];
paulo@0: 	float    range = *nr;
paulo@0: 	float    prob;
paulo@0: 
paulo@0: 	/* make sure we pick at least one */
paulo@0: 	if (!*ret)
paulo@0: 		*ret = node;
paulo@0: 
paulo@0: 	/* set the probability of selecting this node */
paulo@0: 	prob = range * rand() / (RAND_MAX + 1.0);
paulo@0: 
paulo@0: 	if (prob < 1)
paulo@0: 		*ret = node;
paulo@0: 
paulo@0: 	(*nr)++;
paulo@0: 
paulo@0: 	/* we dont use the return value here, because we need to try
paulo@0: 	 * all the nodes, and returning non-null here short-circuits */
paulo@0: 	return NULL;
paulo@0: }
paulo@0: 
paulo@0: /*
paulo@0:  * Pick a node at random that is also of the specified 
paulo@0:  * class and state.
paulo@0:  */
paulo@0: GtNode *gt_conn_random (gt_node_class_t klass, gt_node_state_t state)
paulo@0: {
paulo@0: 	void   *cmp[2];
paulo@0: 	int     nr;   
paulo@0: 	GtNode *ret = NULL;
paulo@0: 
paulo@0: 	/* initial probability */
paulo@0: 	nr = 1;
paulo@0: 
paulo@0: 	cmp[0] = &nr;
paulo@0: 	cmp[1] = &ret;
paulo@0: 
paulo@0: 	gt_conn_foreach (GT_CONN_FOREACH(select_rand), cmp,
paulo@0: 	                 klass, state, 0);
paulo@0: 
paulo@0: 	return ret;
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: static BOOL collect_old (GtNode *node, void **data)
paulo@0: {
paulo@0: 	List   **to_free    = data[0];
paulo@0: 	int     *max_tofree = data[1];
paulo@0: 
paulo@0: 	/* don't make the node list too small */
paulo@0: 	if (*max_tofree == 0)
paulo@0: 		return FALSE;
paulo@0: 
paulo@0: 	if (gt_node_freeable (node))
paulo@0: 	{
paulo@0: 		/* protect the iterator because we're removing a node */
paulo@0: 		move_iterator (node);
paulo@0: 
paulo@0: 		(*max_tofree)--;
paulo@0: 		*to_free = list_append (*to_free, node);
paulo@0: 
paulo@0: 		return TRUE;
paulo@0: 	}
paulo@0: 
paulo@0: 	return FALSE;
paulo@0: }
paulo@0: 
paulo@0: static BOOL dump_node (GtNode *node, void *udata)
paulo@0: {
paulo@0: 	gt_node_free (node);
paulo@0: 	return TRUE;
paulo@0: }
paulo@0: 
paulo@0: /*
paulo@0:  * NOTE: We can't re-descend the node_list by calling gt_node_free [which
paulo@0:  * calls gt_conn_remove->list_remove] while iterating the node_list in
paulo@0:  * list_foreach_remove. So, we build a second a list of nodes to free while
paulo@0:  * removing those from node_list "by hand" and then free that list.
paulo@0:  */
paulo@0: void gt_conn_trim (void)
paulo@0: {
paulo@0: 	List   *to_free     = NULL;
paulo@0: 	int     max_tofree;
paulo@0: 	int     len;
paulo@0: 	void   *data[2];
paulo@0: 
paulo@0: 	len = list_length (node_list);
paulo@0: 	max_tofree = MAX (0, len - 500);
paulo@0: 
paulo@0: 	data[0] = &to_free;
paulo@0: 	data[1] = &max_tofree;
paulo@0: 
paulo@0: 	/* get rid of the oldest nodes first */
paulo@0: 	gt_conn_sort ((CompareFunc)gt_conn_sort_vit_neg);
paulo@0: 
paulo@0: 	node_list = list_foreach_remove (node_list, (ListForeachFunc)collect_old,
paulo@0: 	                                 data);
paulo@0: 
paulo@0: 	GT->DBGFN (GT, "trimming %d/%d nodes", list_length (to_free), len);
paulo@0: 	list_foreach_remove (to_free, (ListForeachFunc)dump_node, NULL);
paulo@0: 
paulo@0: 	/* set the node list back to rights wrt vitality */
paulo@0: 	gt_conn_sort ((CompareFunc)gt_conn_sort_vit);
paulo@0: 
paulo@0: 	/* reset the iterator to some random node */
paulo@0: 	iterator = list_nth (node_list,
paulo@0: 	                     (float)rand() * len / (RAND_MAX + 1.0));
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: int gt_conn_sort_vit (GtNode *a, GtNode *b)
paulo@0: {
paulo@0: 	if (a->vitality > b->vitality)
paulo@0: 		return -1;
paulo@0: 	else if (a->vitality < b->vitality)
paulo@0: 		return 1;
paulo@0: 	else
paulo@0: 		return 0;
paulo@0: }
paulo@0: 
paulo@0: int gt_conn_sort_vit_neg (GtNode *a, GtNode *b)
paulo@0: {
paulo@0: 	return -gt_conn_sort_vit (a, b);
paulo@0: }
paulo@0: 
paulo@0: /* NOTE: this isnt safe to call at all times */
paulo@0: void gt_conn_sort (CompareFunc func)
paulo@0: {
paulo@0: 	node_list = list_sort (node_list, func);
paulo@0: 
paulo@0: 	/* reset the iterator */
paulo@0: 	iterator = NULL;
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: struct _sync_args
paulo@0: {
paulo@0: 	time_t tm;
paulo@0: 	FILE  *f;
paulo@0: };
paulo@0: 
paulo@0: static GtNode *sync_node (TCPC *c, GtNode *node, struct _sync_args *sync)
paulo@0: {
paulo@0: 	size_t ret;
paulo@0: 
paulo@0: 	/* node->vitality is updated lazily, to avoid a syscall for every
paulo@0: 	 * packet.  Maybe this isnt worth it */
paulo@0: 	if (node->state & GT_NODE_CONNECTED)
paulo@0: 		node->vitality = sync->tm;
paulo@0: 
paulo@0: 	/* only cache the node if we have connected to it before successfully */
paulo@0: 	if (node->vitality > 0 &&
paulo@0: 	    node->gt_port > 0)
paulo@0: 	{
paulo@0: 		ret = fprintf (sync->f, "%lu %s:%hu %lu %lu\n", (long)node->vitality,
paulo@0: 		               net_ip_str (node->ip), node->gt_port,
paulo@0: 		               (long)node->size_kb, (long)node->files);
paulo@0: 
paulo@0: 		/* stop iterating if there was an error */
paulo@0: 		if (ret <= 0)
paulo@0: 			return node;
paulo@0: 	}
paulo@0: 
paulo@0: 	return NULL;
paulo@0: }
paulo@0: 
paulo@0: void gt_node_list_save (void)
paulo@0: {
paulo@0: 	struct _sync_args sync;
paulo@0: 	char  *tmp_path;
paulo@0: 
paulo@0: 	time (&sync.tm);
paulo@0: 	tmp_path = STRDUP (gift_conf_path ("Gnutella/nodes.tmp"));
paulo@0: 
paulo@0: 	if (!(sync.f = fopen (gift_conf_path ("Gnutella/nodes.tmp"), "w")))
paulo@0: 	{
paulo@0: 		GT->DBGFN (GT, "error opening tmp file: %s", GIFT_STRERROR ());
paulo@0: 		free (tmp_path);
paulo@0: 		return;
paulo@0: 	}
paulo@0: 
paulo@0: 	/*
paulo@0: 	 * The nodes file is fairly important. Check for errors when writing to
paulo@0: 	 * the disk.
paulo@0: 	 */
paulo@0: 	if (gt_conn_foreach (GT_CONN_FOREACH(sync_node), &sync,
paulo@0: 	                     GT_NODE_NONE, GT_NODE_ANY, 0) != NULL)
paulo@0: 	{
paulo@0: 		GT->warn (GT, "error writing nodes file: %s", GIFT_STRERROR());
paulo@0: 		fclose (sync.f);
paulo@0: 		free (tmp_path);
paulo@0: 		return;
paulo@0: 	}
paulo@0: 
paulo@0: 	if (fclose (sync.f) != 0)
paulo@0: 	{
paulo@0: 		GT->warn (GT, "error closing nodes file: %s", GIFT_STRERROR());
paulo@0: 		free (tmp_path);
paulo@0: 		return;
paulo@0: 	}
paulo@0: 
paulo@0: 	file_mv (tmp_path, gift_conf_path ("Gnutella/nodes"));
paulo@0: 
paulo@0: 	free (tmp_path);
paulo@0: }
paulo@0: 
paulo@0: static void load_nodes (/*const*/ char *conf_path, gt_node_class_t klass)
paulo@0: {
paulo@0: 	GtNode *node;
paulo@0: 	FILE   *f;
paulo@0: 	char   *buf = NULL;
paulo@0: 	char   *ptr;
paulo@0: 
paulo@0: 	f = fopen (gift_conf_path (conf_path), "r");
paulo@0: 
paulo@0: 	/* try the global nodes file */
paulo@0: 	if (!f)
paulo@0: 	{
paulo@0: 		char *filename;
paulo@0: 
paulo@0: 		if (!(filename = malloc (strlen (platform_data_dir ()) + 50)))
paulo@0: 			return;
paulo@0: 
paulo@0: 		sprintf (filename, "%s/%s", platform_data_dir (), conf_path);
paulo@0: 
paulo@0: 		f = fopen (filename, "r");
paulo@0: 
paulo@0: 		free (filename);
paulo@0: 	}
paulo@0: 
paulo@0: 	if (!f)
paulo@0: 		return;
paulo@0: 
paulo@0: 	while (file_read_line (f, &buf))
paulo@0: 	{
paulo@0: 		unsigned long  vitality;
paulo@0: 		in_addr_t      ip;
paulo@0: 		in_port_t      port;
paulo@0: 		uint32_t       size_kb;
paulo@0: 		uint32_t       files;
paulo@0: 
paulo@0: 		ptr = buf;
paulo@0: 
paulo@0: 		/* [vitality] [ip]:[port] [shares size(kB)] [file count] */
paulo@0: 
paulo@0: 		vitality = ATOUL  (string_sep (&ptr, " "));
paulo@0: 		ip       = net_ip (string_sep (&ptr, ":"));
paulo@0: 		port     = ATOI   (string_sep (&ptr, " "));
paulo@0: 		size_kb  = ATOI   (string_sep (&ptr, " "));
paulo@0: 		files    = ATOI   (string_sep (&ptr, " "));
paulo@0: 
paulo@0: 		if (!ip || ip == INADDR_NONE)
paulo@0: 			continue;
paulo@0: 
paulo@0: 		if (size_kb == (uint32_t)-1)
paulo@0: 			size_kb = 0;
paulo@0: 
paulo@0: 		if (files == (uint32_t)-1)
paulo@0: 			files = 0;
paulo@0: 
paulo@0: 		node = gt_node_register (ip, port, klass);
paulo@0: 
paulo@0: 		if (!node)
paulo@0: 			continue;
paulo@0: 
paulo@0: 		node->vitality = vitality;
paulo@0: 
paulo@0: 		node->size_kb  = size_kb;
paulo@0: 		node->files    = files;
paulo@0: 	}
paulo@0: 
paulo@0: 	fclose (f);
paulo@0: }
paulo@0: 
paulo@0: void gt_node_list_load (void)
paulo@0: {
paulo@0: 	load_nodes ("Gnutella/nodes", GT_NODE_ULTRA);
paulo@0: 
paulo@0: 	/* sort the list so we contact the most recent nodes first */
paulo@0: 	gt_conn_sort ((CompareFunc) gt_conn_sort_vit);
paulo@0: }