paulo@0: /*
paulo@0:  * $Id: gt_node_cache.c,v 1.11 2004/03/05 17:58:39 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_cache.h"
paulo@0: 
paulo@0: #include "file_cache.h"
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: #define MAX_RECENT          (150)
paulo@0: #define MAX_STABLE          (30)
paulo@0: 
paulo@0: #define MAX_STICKY_RECENT   (150)
paulo@0: #define MAX_STICKY_STABLE   (30)
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: static List       *recent;
paulo@0: static List       *stable;
paulo@0: 
paulo@0: static List       *sticky_recent;   /* synced to disk */
paulo@0: static List       *sticky_stable;   /* like stable list, but nodes stay */
paulo@0: 
paulo@0: #if 0
paulo@0: static List       *compressible;
paulo@0: #endif
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: static void ipv4_addr_init (struct ipv4_addr *addr, in_addr_t ip,
paulo@0:                             in_port_t port)
paulo@0: {
paulo@0: 	memset (addr, 0, sizeof (struct ipv4_addr));
paulo@0: 
paulo@0: 	addr->ip   = ip;
paulo@0: 	addr->port = port;
paulo@0: }
paulo@0: 
paulo@0: static void cached_node_init (struct cached_node *node, in_addr_t ipv4,
paulo@0:                               in_port_t port, gt_node_class_t klass,
paulo@0:                               time_t timestamp, time_t uptime,
paulo@0:                               in_addr_t src_ip)
paulo@0: {
paulo@0: 	memset (node, 0, sizeof (*node));
paulo@0: 
paulo@0: 	ipv4_addr_init (&node->addr, ipv4, port);
paulo@0: 
paulo@0: 	node->klass     = klass;
paulo@0: 	node->timestamp = timestamp;
paulo@0: 	node->uptime    = uptime;
paulo@0: 	node->src_ip    = src_ip;
paulo@0: }
paulo@0: 
paulo@0: static int cmp_ipv4 (struct cached_node *a, struct cached_node *b)
paulo@0: {
paulo@0: 	return memcmp (&a->addr, &b->addr, sizeof (a->addr));
paulo@0: }
paulo@0: 
paulo@0: static int cmp_recent (struct cached_node *a, struct cached_node *b)
paulo@0: {
paulo@0: 	return INTCMP (b->timestamp, a->timestamp);
paulo@0: }
paulo@0: 
paulo@0: static int cmp_stable (struct cached_node *a, struct cached_node *b)
paulo@0: {
paulo@0: 	time_t a_time, b_time;
paulo@0: 
paulo@0: 	/*
paulo@0: 	 * Assume the node will be up for as much time as it was up
paulo@0: 	 * already, and convert this to a timestamp.
paulo@0: 	 *
paulo@0: 	 * This makes a difference than just comparing the uptime
paulo@0: 	 * because the cache gets synced to disk.
paulo@0: 	 */
paulo@0: 	a_time = a->uptime * 2 + a->timestamp;
paulo@0: 	b_time = b->uptime * 2 + b->timestamp;
paulo@0: 
paulo@0: 	return INTCMP (b_time, a_time);
paulo@0: }
paulo@0: 
paulo@0: static List *add_list (List *list, size_t max_elements, CompareFunc func,
paulo@0:                        struct cached_node *node)
paulo@0: {
paulo@0: 	struct cached_node  *new_node;
paulo@0: 	struct cached_node  *rm;
paulo@0: 	List                *dup;
paulo@0: 	List                *link;
paulo@0: 
paulo@0: 	if ((dup = list_find_custom (list, node, (CompareFunc)cmp_ipv4)))
paulo@0: 	{
paulo@0: 		free (dup->data);
paulo@0: 		list = list_remove_link (list, dup);
paulo@0: 	}
paulo@0: 
paulo@0: 	if (!(new_node = gift_memdup (node, sizeof (struct cached_node))))
paulo@0: 		return list;
paulo@0: 
paulo@0: 	list = list_insert_sorted (list, func, new_node);
paulo@0: 
paulo@0: 	/*
paulo@0: 	 * Truncate list at max_elements.
paulo@0: 	 */
paulo@0: 	link = list_nth (list, max_elements);
paulo@0: 	rm   = list_nth_data (link, 0);
paulo@0: 
paulo@0: 	list = list_remove_link (list, link);
paulo@0: 	free (rm);
paulo@0: 
paulo@0: 	return list;
paulo@0: }
paulo@0: 
paulo@0: static void add_to_cache (struct cached_node *node)
paulo@0: {
paulo@0: 	recent        = add_list (recent, MAX_RECENT,
paulo@0: 	                          (CompareFunc)cmp_recent, node);
paulo@0: 	sticky_recent = add_list (sticky_recent, MAX_STICKY_RECENT,
paulo@0: 	                          (CompareFunc)cmp_recent, node);
paulo@0: 
paulo@0: 	if (node->uptime > 0)
paulo@0: 	{
paulo@0: 		stable        = add_list (stable, MAX_STABLE,
paulo@0: 		                          (CompareFunc)cmp_stable, node);
paulo@0: 		sticky_stable = add_list (sticky_stable, MAX_STICKY_STABLE,
paulo@0: 		                          (CompareFunc)cmp_stable, node);
paulo@0: 	}
paulo@0: }
paulo@0: 
paulo@0: void gt_node_cache_add_ipv4 (in_addr_t ipv4, in_port_t port,
paulo@0:                              gt_node_class_t klass, time_t timestamp,
paulo@0:                              time_t uptime, in_addr_t src_ip)
paulo@0: {
paulo@0: 	struct cached_node node;
paulo@0: 
paulo@0: 	/* make sure we don't add nodes with class GT_NODE_NONE */
paulo@0: 	if (klass == GT_NODE_NONE)
paulo@0: 		klass = GT_NODE_LEAF;
paulo@0: 
paulo@0: 	cached_node_init (&node, ipv4, port, klass, timestamp, uptime, src_ip);
paulo@0: 	add_to_cache (&node);
paulo@0: 
paulo@0: 	/* don't put nodes that are already in the node list in the cache */
paulo@0: 	if (gt_node_lookup (ipv4, port))
paulo@0: 		gt_node_cache_del_ipv4 (ipv4, port);
paulo@0: }
paulo@0: 
paulo@0: static List *del_list (List *list, struct cached_node *node,
paulo@0:                        in_addr_t ipv4, in_port_t port)
paulo@0: {
paulo@0: 	List *link;
paulo@0: 
paulo@0: 	if (!(link = list_find_custom (list, node, (CompareFunc)cmp_ipv4)))
paulo@0: 		return list;
paulo@0: 
paulo@0: 	free (link->data);
paulo@0: 	return list_remove_link (list, link);
paulo@0: }
paulo@0: 
paulo@0: static void del_from_cache (in_addr_t ipv4, in_port_t port)
paulo@0: {
paulo@0: 	struct cached_node node;
paulo@0: 
paulo@0: 	cached_node_init (&node, ipv4, port, GT_NODE_NONE, 0, 0, 0);
paulo@0: 
paulo@0: 	recent = del_list (recent, &node, ipv4, port);
paulo@0: 	stable = del_list (stable, &node, ipv4, port);
paulo@0: }
paulo@0: 
paulo@0: void gt_node_cache_del_ipv4 (in_addr_t ipv4, in_port_t port)
paulo@0: {
paulo@0: 	del_from_cache (ipv4, port);
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: #if 0
paulo@0: static int print_node (struct cached_node *node, String *s)
paulo@0: {
paulo@0: 	char *src;
paulo@0: 
paulo@0: 	src = STRDUP (net_ip_str (node->src_ip));
paulo@0: 
paulo@0: 	string_appendf (s, "[%s:%hu {%s}] ", net_ip_str (node->addr.ip),
paulo@0: 	                node->addr.port, src);
paulo@0: 	free (src);
paulo@0: 
paulo@0: 	return FALSE;
paulo@0: }
paulo@0: 
paulo@0: static void print_list (char *prefix, List *list)
paulo@0: {
paulo@0: 	String *s;
paulo@0: 
paulo@0: 	if (!(s = string_new (NULL, 0, 0, TRUE)))
paulo@0: 	      return;
paulo@0: 
paulo@0: 	string_append (s, prefix);
paulo@0: 
paulo@0: 	list_foreach (list, (ListForeachFunc)print_node, s);
paulo@0: 	GT->dbg (GT, "%s", s->str);
paulo@0: 
paulo@0: 	string_free (s);
paulo@0: }
paulo@0: #endif
paulo@0: 
paulo@0: void gt_node_cache_trace (void)
paulo@0: {
paulo@0: #if 0
paulo@0: 	print_list ("recent: ", recent);
paulo@0: 	print_list ("stable: ", stable);
paulo@0: 	print_list ("sticky_recent: ", sticky_recent);
paulo@0: 	print_list ("sticky_stable: ", sticky_stable);
paulo@0: #endif
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: /* return some nodes from the cache, and remove them */
paulo@0: size_t get_first (List **src_list, List **dst_list, size_t nr)
paulo@0: {
paulo@0: 	struct cached_node *node;
paulo@0: 	struct cached_node *dup;
paulo@0: 
paulo@0: 	node = list_nth_data (*src_list, 0);
paulo@0: 
paulo@0: 	if (!node || !(dup = gift_memdup (node, sizeof (*node))))
paulo@0: 		return nr;
paulo@0: 
paulo@0: 	*dst_list = list_prepend (*dst_list, dup);
paulo@0: 	nr--;
paulo@0: 
paulo@0: 	gt_node_cache_del_ipv4 (node->addr.ip, node->addr.port);
paulo@0: 	return nr;
paulo@0: }
paulo@0: 
paulo@0: /*
paulo@0:  * Remove some elements from the cache and return them in a list .
paulo@0:  *
paulo@0:  * The nodes and the list returned SHOULD be freed.
paulo@0:  */
paulo@0: List *gt_node_cache_get_remove (size_t nr)
paulo@0: {
paulo@0: 	List *list = NULL;
paulo@0: 
paulo@0: 	/*
paulo@0: 	 * We check the recent list first, and then if that's empty check the
paulo@0: 	 * stable list, so we don't end up checking the stable list all the time.
paulo@0: 	 */
paulo@0: 	while (nr > 0 && recent != NULL)
paulo@0: 		nr = get_first (&recent, &list, nr);
paulo@0: 
paulo@0: 	while (nr > 0 && stable != NULL)
paulo@0: 		nr = get_first (&stable, &list, nr);
paulo@0: 
paulo@0: 	return list;
paulo@0: }
paulo@0: 
paulo@0: /*
paulo@0:  * Return some elements from the cache in a list
paulo@0:  *
paulo@0:  * NOTE: the data in the list returned SHOULD NOT be freed
paulo@0:  */
paulo@0: List *gt_node_cache_get (size_t nr)
paulo@0: {
paulo@0: 	List    *list = NULL;
paulo@0: 	size_t   len;
paulo@0: 	int      index;
paulo@0: 
paulo@0: 	len = list_length (sticky_recent);
paulo@0: 
paulo@0: 	/*
paulo@0: 	 * If we don't have more than twice the number of nodes, just return an
paulo@0: 	 * offset in the list of recent nodes.
paulo@0: 	 *
paulo@0: 	 * This is done so we can use the simple (stupid) selection algorithm
paulo@0: 	 * below that would be inefficient otherwise.
paulo@0: 	 */
paulo@0: 	if (len / 2 < nr)
paulo@0: 		return list_copy (list_nth (sticky_recent, MAX (0, len - nr)));
paulo@0: 
paulo@0: 	while (nr > 0)
paulo@0: 	{
paulo@0: 		struct cached_node *node;
paulo@0: 
paulo@0: 		index = (float)len * rand() / (RAND_MAX + 1.0);
paulo@0: 
paulo@0: 		node = list_nth_data (sticky_recent, index);
paulo@0: 		assert (node != NULL);
paulo@0: 
paulo@0: 		if (list_find (list, node))
paulo@0: 			continue;
paulo@0: 
paulo@0: 		list = list_append (list, node);
paulo@0: 		nr--;
paulo@0: 	}
paulo@0: 
paulo@0: 	return list;
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: static char *node_cache_file (const char *name)
paulo@0: {
paulo@0: 	return gift_conf_path ("Gnutella/%s", name);
paulo@0: }
paulo@0: 
paulo@0: /*
paulo@0:  * Store the cache data in the dataset. The ip:port as a string
paulo@0:  * is used as a key.
paulo@0:  */
paulo@0: static BOOL write_line (struct cached_node *node, FileCache *cache)
paulo@0: {
paulo@0: 	char *ip_port;
paulo@0: 	char *line;
paulo@0: 
paulo@0: 	ip_port = stringf_dup ("%s:%hu", net_ip_str (node->addr.ip),
paulo@0: 	                       node->addr.port);
paulo@0: 
paulo@0: 	if (!ip_port)
paulo@0: 		return FALSE;
paulo@0: 
paulo@0: 	line = stringf_dup ("%s %lu %lu %s", gt_node_class_str (node->klass),
paulo@0: 	                    (long)node->timestamp, (long)node->uptime,
paulo@0: 	                    net_ip_str (node->src_ip));
paulo@0: 
paulo@0: 	if (!line)
paulo@0: 	{
paulo@0: 		free (ip_port);
paulo@0: 		return FALSE;
paulo@0: 	}
paulo@0: 
paulo@0: 	file_cache_insert (cache, ip_port, line);
paulo@0: 
paulo@0: 	free (ip_port);
paulo@0: 	free (line);
paulo@0: 
paulo@0: 	return FALSE;
paulo@0: }
paulo@0: 
paulo@0: /*
paulo@0:  * Read in a line from a cache file.
paulo@0:  *
paulo@0:  * The ip:port is the key in the Dataset. The value
paulo@0:  * is everything else that dsecribe an entry in the node
paulo@0:  * cache, as a string.
paulo@0:  */
paulo@0: static void parse_line (ds_data_t *key, ds_data_t *value, void *udata)
paulo@0: {
paulo@0: 	char      *ip_port = key->data;
paulo@0: 	char      *str     = value->data;
paulo@0: 	in_addr_t  ipv4;
paulo@0: 	in_port_t  port;
paulo@0: 	time_t     timestamp;
paulo@0: 	time_t     uptime;
paulo@0: 	in_addr_t  src_ip;
paulo@0: 	char      *klass;
paulo@0: 
paulo@0: 	ipv4 = net_ip (string_sep (&ip_port, ":"));
paulo@0: 	port = ATOUL  (ip_port);
paulo@0: 
paulo@0: 	if (ipv4 == 0 || ipv4 == INADDR_NONE || port == 0)
paulo@0: 		return;
paulo@0: 
paulo@0: 	/* NOTE: we ignore the class string for now */
paulo@0: 	klass     =         string_sep (&str, " ");
paulo@0: 	timestamp = ATOUL  (string_sep (&str, " "));
paulo@0: 	uptime    = ATOUL  (string_sep (&str, " "));
paulo@0: 	src_ip    = net_ip (string_sep (&str, " "));
paulo@0: 
paulo@0: 	if (!klass || timestamp == 0)
paulo@0: 		return;
paulo@0: 
paulo@0: 	/* add it to the cache */
paulo@0: 	gt_node_cache_add_ipv4 (ipv4, port, GT_NODE_ULTRA, timestamp, uptime,
paulo@0: 	                        src_ip);
paulo@0: }
paulo@0: 
paulo@0: static BOOL load_cache (char *name)
paulo@0: {
paulo@0: 	FileCache  *cache;
paulo@0: 	char       *file;
paulo@0: 
paulo@0: 	file  = node_cache_file (name);
paulo@0: 	cache = file_cache_new (file);
paulo@0: 
paulo@0: 	if (!cache)
paulo@0: 		return FALSE;
paulo@0: 
paulo@0: 	dataset_foreach (cache->d, DS_FOREACH(parse_line), NULL);
paulo@0: 
paulo@0: 	file_cache_free (cache);
paulo@0: 	return TRUE;
paulo@0: }
paulo@0: 
paulo@0: static BOOL save_cache (char *name, List *list)
paulo@0: {
paulo@0: 	FileCache  *cache;
paulo@0: 	char       *file;
paulo@0: 
paulo@0: 	file  = node_cache_file (name);
paulo@0: 	cache = file_cache_new (file);
paulo@0: 
paulo@0: 	/* flush the existing data (in memory, only) */
paulo@0: 	file_cache_flush (cache);
paulo@0: 
paulo@0: 	/* save each entry in the node cache to the file cache */
paulo@0: 	list_foreach (list, (ListForeachFunc)write_line, cache);
paulo@0: 
paulo@0: 	if (!file_cache_sync (cache))
paulo@0: 	{
paulo@0: 		GT->DBGFN (GT, "error saving cache \"%s\": %s", name, GIFT_STRERROR());
paulo@0: 		return FALSE;
paulo@0: 	}
paulo@0: 
paulo@0: 	file_cache_free (cache);
paulo@0: 
paulo@0: 	return TRUE;
paulo@0: }
paulo@0: 
paulo@0: void gt_node_cache_load (void)
paulo@0: {
paulo@0: 	load_cache ("stable_nodes");
paulo@0: 	load_cache ("recent_nodes");
paulo@0: }
paulo@0: 
paulo@0: void gt_node_cache_save (void)
paulo@0: {
paulo@0: 	save_cache ("stable_nodes", sticky_stable);
paulo@0: 	save_cache ("recent_nodes", sticky_recent);
paulo@0: }
paulo@0: 
paulo@0: /*****************************************************************************/
paulo@0: 
paulo@0: void gt_node_cache_init (void)
paulo@0: {
paulo@0: 	gt_node_cache_load ();
paulo@0: }
paulo@0: 
paulo@0: void gt_node_cache_cleanup (void)
paulo@0: {
paulo@0: 	gt_node_cache_save ();
paulo@0: 
paulo@0: 	/* TODO: free node cache lists */
paulo@0: }