1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/gt_node_cache.c	Sat Feb 20 21:18:28 2010 -0800
     1.3 @@ -0,0 +1,459 @@
     1.4 +/*
     1.5 + * $Id: gt_node_cache.c,v 1.11 2004/03/05 17:58:39 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_cache.h"
    1.24 +
    1.25 +#include "file_cache.h"
    1.26 +
    1.27 +/*****************************************************************************/
    1.28 +
    1.29 +#define MAX_RECENT          (150)
    1.30 +#define MAX_STABLE          (30)
    1.31 +
    1.32 +#define MAX_STICKY_RECENT   (150)
    1.33 +#define MAX_STICKY_STABLE   (30)
    1.34 +
    1.35 +/*****************************************************************************/
    1.36 +
    1.37 +static List       *recent;
    1.38 +static List       *stable;
    1.39 +
    1.40 +static List       *sticky_recent;   /* synced to disk */
    1.41 +static List       *sticky_stable;   /* like stable list, but nodes stay */
    1.42 +
    1.43 +#if 0
    1.44 +static List       *compressible;
    1.45 +#endif
    1.46 +
    1.47 +/*****************************************************************************/
    1.48 +
    1.49 +static void ipv4_addr_init (struct ipv4_addr *addr, in_addr_t ip,
    1.50 +                            in_port_t port)
    1.51 +{
    1.52 +	memset (addr, 0, sizeof (struct ipv4_addr));
    1.53 +
    1.54 +	addr->ip   = ip;
    1.55 +	addr->port = port;
    1.56 +}
    1.57 +
    1.58 +static void cached_node_init (struct cached_node *node, in_addr_t ipv4,
    1.59 +                              in_port_t port, gt_node_class_t klass,
    1.60 +                              time_t timestamp, time_t uptime,
    1.61 +                              in_addr_t src_ip)
    1.62 +{
    1.63 +	memset (node, 0, sizeof (*node));
    1.64 +
    1.65 +	ipv4_addr_init (&node->addr, ipv4, port);
    1.66 +
    1.67 +	node->klass     = klass;
    1.68 +	node->timestamp = timestamp;
    1.69 +	node->uptime    = uptime;
    1.70 +	node->src_ip    = src_ip;
    1.71 +}
    1.72 +
    1.73 +static int cmp_ipv4 (struct cached_node *a, struct cached_node *b)
    1.74 +{
    1.75 +	return memcmp (&a->addr, &b->addr, sizeof (a->addr));
    1.76 +}
    1.77 +
    1.78 +static int cmp_recent (struct cached_node *a, struct cached_node *b)
    1.79 +{
    1.80 +	return INTCMP (b->timestamp, a->timestamp);
    1.81 +}
    1.82 +
    1.83 +static int cmp_stable (struct cached_node *a, struct cached_node *b)
    1.84 +{
    1.85 +	time_t a_time, b_time;
    1.86 +
    1.87 +	/*
    1.88 +	 * Assume the node will be up for as much time as it was up
    1.89 +	 * already, and convert this to a timestamp.
    1.90 +	 *
    1.91 +	 * This makes a difference than just comparing the uptime
    1.92 +	 * because the cache gets synced to disk.
    1.93 +	 */
    1.94 +	a_time = a->uptime * 2 + a->timestamp;
    1.95 +	b_time = b->uptime * 2 + b->timestamp;
    1.96 +
    1.97 +	return INTCMP (b_time, a_time);
    1.98 +}
    1.99 +
   1.100 +static List *add_list (List *list, size_t max_elements, CompareFunc func,
   1.101 +                       struct cached_node *node)
   1.102 +{
   1.103 +	struct cached_node  *new_node;
   1.104 +	struct cached_node  *rm;
   1.105 +	List                *dup;
   1.106 +	List                *link;
   1.107 +
   1.108 +	if ((dup = list_find_custom (list, node, (CompareFunc)cmp_ipv4)))
   1.109 +	{
   1.110 +		free (dup->data);
   1.111 +		list = list_remove_link (list, dup);
   1.112 +	}
   1.113 +
   1.114 +	if (!(new_node = gift_memdup (node, sizeof (struct cached_node))))
   1.115 +		return list;
   1.116 +
   1.117 +	list = list_insert_sorted (list, func, new_node);
   1.118 +
   1.119 +	/*
   1.120 +	 * Truncate list at max_elements.
   1.121 +	 */
   1.122 +	link = list_nth (list, max_elements);
   1.123 +	rm   = list_nth_data (link, 0);
   1.124 +
   1.125 +	list = list_remove_link (list, link);
   1.126 +	free (rm);
   1.127 +
   1.128 +	return list;
   1.129 +}
   1.130 +
   1.131 +static void add_to_cache (struct cached_node *node)
   1.132 +{
   1.133 +	recent        = add_list (recent, MAX_RECENT,
   1.134 +	                          (CompareFunc)cmp_recent, node);
   1.135 +	sticky_recent = add_list (sticky_recent, MAX_STICKY_RECENT,
   1.136 +	                          (CompareFunc)cmp_recent, node);
   1.137 +
   1.138 +	if (node->uptime > 0)
   1.139 +	{
   1.140 +		stable        = add_list (stable, MAX_STABLE,
   1.141 +		                          (CompareFunc)cmp_stable, node);
   1.142 +		sticky_stable = add_list (sticky_stable, MAX_STICKY_STABLE,
   1.143 +		                          (CompareFunc)cmp_stable, node);
   1.144 +	}
   1.145 +}
   1.146 +
   1.147 +void gt_node_cache_add_ipv4 (in_addr_t ipv4, in_port_t port,
   1.148 +                             gt_node_class_t klass, time_t timestamp,
   1.149 +                             time_t uptime, in_addr_t src_ip)
   1.150 +{
   1.151 +	struct cached_node node;
   1.152 +
   1.153 +	/* make sure we don't add nodes with class GT_NODE_NONE */
   1.154 +	if (klass == GT_NODE_NONE)
   1.155 +		klass = GT_NODE_LEAF;
   1.156 +
   1.157 +	cached_node_init (&node, ipv4, port, klass, timestamp, uptime, src_ip);
   1.158 +	add_to_cache (&node);
   1.159 +
   1.160 +	/* don't put nodes that are already in the node list in the cache */
   1.161 +	if (gt_node_lookup (ipv4, port))
   1.162 +		gt_node_cache_del_ipv4 (ipv4, port);
   1.163 +}
   1.164 +
   1.165 +static List *del_list (List *list, struct cached_node *node,
   1.166 +                       in_addr_t ipv4, in_port_t port)
   1.167 +{
   1.168 +	List *link;
   1.169 +
   1.170 +	if (!(link = list_find_custom (list, node, (CompareFunc)cmp_ipv4)))
   1.171 +		return list;
   1.172 +
   1.173 +	free (link->data);
   1.174 +	return list_remove_link (list, link);
   1.175 +}
   1.176 +
   1.177 +static void del_from_cache (in_addr_t ipv4, in_port_t port)
   1.178 +{
   1.179 +	struct cached_node node;
   1.180 +
   1.181 +	cached_node_init (&node, ipv4, port, GT_NODE_NONE, 0, 0, 0);
   1.182 +
   1.183 +	recent = del_list (recent, &node, ipv4, port);
   1.184 +	stable = del_list (stable, &node, ipv4, port);
   1.185 +}
   1.186 +
   1.187 +void gt_node_cache_del_ipv4 (in_addr_t ipv4, in_port_t port)
   1.188 +{
   1.189 +	del_from_cache (ipv4, port);
   1.190 +}
   1.191 +
   1.192 +/*****************************************************************************/
   1.193 +
   1.194 +#if 0
   1.195 +static int print_node (struct cached_node *node, String *s)
   1.196 +{
   1.197 +	char *src;
   1.198 +
   1.199 +	src = STRDUP (net_ip_str (node->src_ip));
   1.200 +
   1.201 +	string_appendf (s, "[%s:%hu {%s}] ", net_ip_str (node->addr.ip),
   1.202 +	                node->addr.port, src);
   1.203 +	free (src);
   1.204 +
   1.205 +	return FALSE;
   1.206 +}
   1.207 +
   1.208 +static void print_list (char *prefix, List *list)
   1.209 +{
   1.210 +	String *s;
   1.211 +
   1.212 +	if (!(s = string_new (NULL, 0, 0, TRUE)))
   1.213 +	      return;
   1.214 +
   1.215 +	string_append (s, prefix);
   1.216 +
   1.217 +	list_foreach (list, (ListForeachFunc)print_node, s);
   1.218 +	GT->dbg (GT, "%s", s->str);
   1.219 +
   1.220 +	string_free (s);
   1.221 +}
   1.222 +#endif
   1.223 +
   1.224 +void gt_node_cache_trace (void)
   1.225 +{
   1.226 +#if 0
   1.227 +	print_list ("recent: ", recent);
   1.228 +	print_list ("stable: ", stable);
   1.229 +	print_list ("sticky_recent: ", sticky_recent);
   1.230 +	print_list ("sticky_stable: ", sticky_stable);
   1.231 +#endif
   1.232 +}
   1.233 +
   1.234 +/*****************************************************************************/
   1.235 +
   1.236 +/* return some nodes from the cache, and remove them */
   1.237 +size_t get_first (List **src_list, List **dst_list, size_t nr)
   1.238 +{
   1.239 +	struct cached_node *node;
   1.240 +	struct cached_node *dup;
   1.241 +
   1.242 +	node = list_nth_data (*src_list, 0);
   1.243 +
   1.244 +	if (!node || !(dup = gift_memdup (node, sizeof (*node))))
   1.245 +		return nr;
   1.246 +
   1.247 +	*dst_list = list_prepend (*dst_list, dup);
   1.248 +	nr--;
   1.249 +
   1.250 +	gt_node_cache_del_ipv4 (node->addr.ip, node->addr.port);
   1.251 +	return nr;
   1.252 +}
   1.253 +
   1.254 +/*
   1.255 + * Remove some elements from the cache and return them in a list .
   1.256 + *
   1.257 + * The nodes and the list returned SHOULD be freed.
   1.258 + */
   1.259 +List *gt_node_cache_get_remove (size_t nr)
   1.260 +{
   1.261 +	List *list = NULL;
   1.262 +
   1.263 +	/*
   1.264 +	 * We check the recent list first, and then if that's empty check the
   1.265 +	 * stable list, so we don't end up checking the stable list all the time.
   1.266 +	 */
   1.267 +	while (nr > 0 && recent != NULL)
   1.268 +		nr = get_first (&recent, &list, nr);
   1.269 +
   1.270 +	while (nr > 0 && stable != NULL)
   1.271 +		nr = get_first (&stable, &list, nr);
   1.272 +
   1.273 +	return list;
   1.274 +}
   1.275 +
   1.276 +/*
   1.277 + * Return some elements from the cache in a list
   1.278 + *
   1.279 + * NOTE: the data in the list returned SHOULD NOT be freed
   1.280 + */
   1.281 +List *gt_node_cache_get (size_t nr)
   1.282 +{
   1.283 +	List    *list = NULL;
   1.284 +	size_t   len;
   1.285 +	int      index;
   1.286 +
   1.287 +	len = list_length (sticky_recent);
   1.288 +
   1.289 +	/*
   1.290 +	 * If we don't have more than twice the number of nodes, just return an
   1.291 +	 * offset in the list of recent nodes.
   1.292 +	 *
   1.293 +	 * This is done so we can use the simple (stupid) selection algorithm
   1.294 +	 * below that would be inefficient otherwise.
   1.295 +	 */
   1.296 +	if (len / 2 < nr)
   1.297 +		return list_copy (list_nth (sticky_recent, MAX (0, len - nr)));
   1.298 +
   1.299 +	while (nr > 0)
   1.300 +	{
   1.301 +		struct cached_node *node;
   1.302 +
   1.303 +		index = (float)len * rand() / (RAND_MAX + 1.0);
   1.304 +
   1.305 +		node = list_nth_data (sticky_recent, index);
   1.306 +		assert (node != NULL);
   1.307 +
   1.308 +		if (list_find (list, node))
   1.309 +			continue;
   1.310 +
   1.311 +		list = list_append (list, node);
   1.312 +		nr--;
   1.313 +	}
   1.314 +
   1.315 +	return list;
   1.316 +}
   1.317 +
   1.318 +/*****************************************************************************/
   1.319 +
   1.320 +static char *node_cache_file (const char *name)
   1.321 +{
   1.322 +	return gift_conf_path ("Gnutella/%s", name);
   1.323 +}
   1.324 +
   1.325 +/*
   1.326 + * Store the cache data in the dataset. The ip:port as a string
   1.327 + * is used as a key.
   1.328 + */
   1.329 +static BOOL write_line (struct cached_node *node, FileCache *cache)
   1.330 +{
   1.331 +	char *ip_port;
   1.332 +	char *line;
   1.333 +
   1.334 +	ip_port = stringf_dup ("%s:%hu", net_ip_str (node->addr.ip),
   1.335 +	                       node->addr.port);
   1.336 +
   1.337 +	if (!ip_port)
   1.338 +		return FALSE;
   1.339 +
   1.340 +	line = stringf_dup ("%s %lu %lu %s", gt_node_class_str (node->klass),
   1.341 +	                    (long)node->timestamp, (long)node->uptime,
   1.342 +	                    net_ip_str (node->src_ip));
   1.343 +
   1.344 +	if (!line)
   1.345 +	{
   1.346 +		free (ip_port);
   1.347 +		return FALSE;
   1.348 +	}
   1.349 +
   1.350 +	file_cache_insert (cache, ip_port, line);
   1.351 +
   1.352 +	free (ip_port);
   1.353 +	free (line);
   1.354 +
   1.355 +	return FALSE;
   1.356 +}
   1.357 +
   1.358 +/*
   1.359 + * Read in a line from a cache file.
   1.360 + *
   1.361 + * The ip:port is the key in the Dataset. The value
   1.362 + * is everything else that dsecribe an entry in the node
   1.363 + * cache, as a string.
   1.364 + */
   1.365 +static void parse_line (ds_data_t *key, ds_data_t *value, void *udata)
   1.366 +{
   1.367 +	char      *ip_port = key->data;
   1.368 +	char      *str     = value->data;
   1.369 +	in_addr_t  ipv4;
   1.370 +	in_port_t  port;
   1.371 +	time_t     timestamp;
   1.372 +	time_t     uptime;
   1.373 +	in_addr_t  src_ip;
   1.374 +	char      *klass;
   1.375 +
   1.376 +	ipv4 = net_ip (string_sep (&ip_port, ":"));
   1.377 +	port = ATOUL  (ip_port);
   1.378 +
   1.379 +	if (ipv4 == 0 || ipv4 == INADDR_NONE || port == 0)
   1.380 +		return;
   1.381 +
   1.382 +	/* NOTE: we ignore the class string for now */
   1.383 +	klass     =         string_sep (&str, " ");
   1.384 +	timestamp = ATOUL  (string_sep (&str, " "));
   1.385 +	uptime    = ATOUL  (string_sep (&str, " "));
   1.386 +	src_ip    = net_ip (string_sep (&str, " "));
   1.387 +
   1.388 +	if (!klass || timestamp == 0)
   1.389 +		return;
   1.390 +
   1.391 +	/* add it to the cache */
   1.392 +	gt_node_cache_add_ipv4 (ipv4, port, GT_NODE_ULTRA, timestamp, uptime,
   1.393 +	                        src_ip);
   1.394 +}
   1.395 +
   1.396 +static BOOL load_cache (char *name)
   1.397 +{
   1.398 +	FileCache  *cache;
   1.399 +	char       *file;
   1.400 +
   1.401 +	file  = node_cache_file (name);
   1.402 +	cache = file_cache_new (file);
   1.403 +
   1.404 +	if (!cache)
   1.405 +		return FALSE;
   1.406 +
   1.407 +	dataset_foreach (cache->d, DS_FOREACH(parse_line), NULL);
   1.408 +
   1.409 +	file_cache_free (cache);
   1.410 +	return TRUE;
   1.411 +}
   1.412 +
   1.413 +static BOOL save_cache (char *name, List *list)
   1.414 +{
   1.415 +	FileCache  *cache;
   1.416 +	char       *file;
   1.417 +
   1.418 +	file  = node_cache_file (name);
   1.419 +	cache = file_cache_new (file);
   1.420 +
   1.421 +	/* flush the existing data (in memory, only) */
   1.422 +	file_cache_flush (cache);
   1.423 +
   1.424 +	/* save each entry in the node cache to the file cache */
   1.425 +	list_foreach (list, (ListForeachFunc)write_line, cache);
   1.426 +
   1.427 +	if (!file_cache_sync (cache))
   1.428 +	{
   1.429 +		GT->DBGFN (GT, "error saving cache \"%s\": %s", name, GIFT_STRERROR());
   1.430 +		return FALSE;
   1.431 +	}
   1.432 +
   1.433 +	file_cache_free (cache);
   1.434 +
   1.435 +	return TRUE;
   1.436 +}
   1.437 +
   1.438 +void gt_node_cache_load (void)
   1.439 +{
   1.440 +	load_cache ("stable_nodes");
   1.441 +	load_cache ("recent_nodes");
   1.442 +}
   1.443 +
   1.444 +void gt_node_cache_save (void)
   1.445 +{
   1.446 +	save_cache ("stable_nodes", sticky_stable);
   1.447 +	save_cache ("recent_nodes", sticky_recent);
   1.448 +}
   1.449 +
   1.450 +/*****************************************************************************/
   1.451 +
   1.452 +void gt_node_cache_init (void)
   1.453 +{
   1.454 +	gt_node_cache_load ();
   1.455 +}
   1.456 +
   1.457 +void gt_node_cache_cleanup (void)
   1.458 +{
   1.459 +	gt_node_cache_save ();
   1.460 +
   1.461 +	/* TODO: free node cache lists */
   1.462 +}