Mercurial > hg > index.fcgi > gift-gnutella > gift-gnutella-0.0.11-1pba

annotate src/gt_node_cache.c @ 0:d39e1d0d75b6

find changesets by author, revision, files, or words in the commit message
initial add
author paulo@hit-nxdomain.opendns.com
date Sat, 20 Feb 2010 21:18:28 -0800
parents
children
rev   line source
paulo@0 1 /*
paulo@0 2 * $Id: gt_node_cache.c,v 1.11 2004/03/05 17:58:39 hipnod Exp $
paulo@0 3 *
paulo@0 4 * Copyright (C) 2001-2003 giFT project (gift.sourceforge.net)
paulo@0 5 *
paulo@0 6 * This program is free software; you can redistribute it and/or modify it
paulo@0 7 * under the terms of the GNU General Public License as published by the
paulo@0 8 * Free Software Foundation; either version 2, or (at your option) any
paulo@0 9 * later version.
paulo@0 10 *
paulo@0 11 * This program is distributed in the hope that it will be useful, but
paulo@0 12 * WITHOUT ANY WARRANTY; without even the implied warranty of
paulo@0 13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
paulo@0 14 * General Public License for more details.
paulo@0 15 */
paulo@0 16
paulo@0 17 #include "gt_gnutella.h"
paulo@0 18
paulo@0 19 #include "gt_node.h"
paulo@0 20 #include "gt_node_cache.h"
paulo@0 21
paulo@0 22 #include "file_cache.h"
paulo@0 23
paulo@0 24 /*****************************************************************************/
paulo@0 25
paulo@0 26 #define MAX_RECENT (150)
paulo@0 27 #define MAX_STABLE (30)
paulo@0 28
paulo@0 29 #define MAX_STICKY_RECENT (150)
paulo@0 30 #define MAX_STICKY_STABLE (30)
paulo@0 31
paulo@0 32 /*****************************************************************************/
paulo@0 33
paulo@0 34 static List *recent;
paulo@0 35 static List *stable;
paulo@0 36
paulo@0 37 static List *sticky_recent; /* synced to disk */
paulo@0 38 static List *sticky_stable; /* like stable list, but nodes stay */
paulo@0 39
paulo@0 40 #if 0
paulo@0 41 static List *compressible;
paulo@0 42 #endif
paulo@0 43
paulo@0 44 /*****************************************************************************/
paulo@0 45
paulo@0 46 static void ipv4_addr_init (struct ipv4_addr *addr, in_addr_t ip,
paulo@0 47 in_port_t port)
paulo@0 48 {
paulo@0 49 memset (addr, 0, sizeof (struct ipv4_addr));
paulo@0 50
paulo@0 51 addr->ip = ip;
paulo@0 52 addr->port = port;
paulo@0 53 }
paulo@0 54
paulo@0 55 static void cached_node_init (struct cached_node *node, in_addr_t ipv4,
paulo@0 56 in_port_t port, gt_node_class_t klass,
paulo@0 57 time_t timestamp, time_t uptime,
paulo@0 58 in_addr_t src_ip)
paulo@0 59 {
paulo@0 60 memset (node, 0, sizeof (*node));
paulo@0 61
paulo@0 62 ipv4_addr_init (&node->addr, ipv4, port);
paulo@0 63
paulo@0 64 node->klass = klass;
paulo@0 65 node->timestamp = timestamp;
paulo@0 66 node->uptime = uptime;
paulo@0 67 node->src_ip = src_ip;
paulo@0 68 }
paulo@0 69
paulo@0 70 static int cmp_ipv4 (struct cached_node *a, struct cached_node *b)
paulo@0 71 {
paulo@0 72 return memcmp (&a->addr, &b->addr, sizeof (a->addr));
paulo@0 73 }
paulo@0 74
paulo@0 75 static int cmp_recent (struct cached_node *a, struct cached_node *b)
paulo@0 76 {
paulo@0 77 return INTCMP (b->timestamp, a->timestamp);
paulo@0 78 }
paulo@0 79
paulo@0 80 static int cmp_stable (struct cached_node *a, struct cached_node *b)
paulo@0 81 {
paulo@0 82 time_t a_time, b_time;
paulo@0 83
paulo@0 84 /*
paulo@0 85 * Assume the node will be up for as much time as it was up
paulo@0 86 * already, and convert this to a timestamp.
paulo@0 87 *
paulo@0 88 * This makes a difference than just comparing the uptime
paulo@0 89 * because the cache gets synced to disk.
paulo@0 90 */
paulo@0 91 a_time = a->uptime * 2 + a->timestamp;
paulo@0 92 b_time = b->uptime * 2 + b->timestamp;
paulo@0 93
paulo@0 94 return INTCMP (b_time, a_time);
paulo@0 95 }
paulo@0 96
paulo@0 97 static List *add_list (List *list, size_t max_elements, CompareFunc func,
paulo@0 98 struct cached_node *node)
paulo@0 99 {
paulo@0 100 struct cached_node *new_node;
paulo@0 101 struct cached_node *rm;
paulo@0 102 List *dup;
paulo@0 103 List *link;
paulo@0 104
paulo@0 105 if ((dup = list_find_custom (list, node, (CompareFunc)cmp_ipv4)))
paulo@0 106 {
paulo@0 107 free (dup->data);
paulo@0 108 list = list_remove_link (list, dup);
paulo@0 109 }
paulo@0 110
paulo@0 111 if (!(new_node = gift_memdup (node, sizeof (struct cached_node))))
paulo@0 112 return list;
paulo@0 113
paulo@0 114 list = list_insert_sorted (list, func, new_node);
paulo@0 115
paulo@0 116 /*
paulo@0 117 * Truncate list at max_elements.
paulo@0 118 */
paulo@0 119 link = list_nth (list, max_elements);
paulo@0 120 rm = list_nth_data (link, 0);
paulo@0 121
paulo@0 122 list = list_remove_link (list, link);
paulo@0 123 free (rm);
paulo@0 124
paulo@0 125 return list;
paulo@0 126 }
paulo@0 127
paulo@0 128 static void add_to_cache (struct cached_node *node)
paulo@0 129 {
paulo@0 130 recent = add_list (recent, MAX_RECENT,
paulo@0 131 (CompareFunc)cmp_recent, node);
paulo@0 132 sticky_recent = add_list (sticky_recent, MAX_STICKY_RECENT,
paulo@0 133 (CompareFunc)cmp_recent, node);
paulo@0 134
paulo@0 135 if (node->uptime > 0)
paulo@0 136 {
paulo@0 137 stable = add_list (stable, MAX_STABLE,
paulo@0 138 (CompareFunc)cmp_stable, node);
paulo@0 139 sticky_stable = add_list (sticky_stable, MAX_STICKY_STABLE,
paulo@0 140 (CompareFunc)cmp_stable, node);
paulo@0 141 }
paulo@0 142 }
paulo@0 143
paulo@0 144 void gt_node_cache_add_ipv4 (in_addr_t ipv4, in_port_t port,
paulo@0 145 gt_node_class_t klass, time_t timestamp,
paulo@0 146 time_t uptime, in_addr_t src_ip)
paulo@0 147 {
paulo@0 148 struct cached_node node;
paulo@0 149
paulo@0 150 /* make sure we don't add nodes with class GT_NODE_NONE */
paulo@0 151 if (klass == GT_NODE_NONE)
paulo@0 152 klass = GT_NODE_LEAF;
paulo@0 153
paulo@0 154 cached_node_init (&node, ipv4, port, klass, timestamp, uptime, src_ip);
paulo@0 155 add_to_cache (&node);
paulo@0 156
paulo@0 157 /* don't put nodes that are already in the node list in the cache */
paulo@0 158 if (gt_node_lookup (ipv4, port))
paulo@0 159 gt_node_cache_del_ipv4 (ipv4, port);
paulo@0 160 }
paulo@0 161
paulo@0 162 static List *del_list (List *list, struct cached_node *node,
paulo@0 163 in_addr_t ipv4, in_port_t port)
paulo@0 164 {
paulo@0 165 List *link;
paulo@0 166
paulo@0 167 if (!(link = list_find_custom (list, node, (CompareFunc)cmp_ipv4)))
paulo@0 168 return list;
paulo@0 169
paulo@0 170 free (link->data);
paulo@0 171 return list_remove_link (list, link);
paulo@0 172 }
paulo@0 173
paulo@0 174 static void del_from_cache (in_addr_t ipv4, in_port_t port)
paulo@0 175 {
paulo@0 176 struct cached_node node;
paulo@0 177
paulo@0 178 cached_node_init (&node, ipv4, port, GT_NODE_NONE, 0, 0, 0);
paulo@0 179
paulo@0 180 recent = del_list (recent, &node, ipv4, port);
paulo@0 181 stable = del_list (stable, &node, ipv4, port);
paulo@0 182 }
paulo@0 183
paulo@0 184 void gt_node_cache_del_ipv4 (in_addr_t ipv4, in_port_t port)
paulo@0 185 {
paulo@0 186 del_from_cache (ipv4, port);
paulo@0 187 }
paulo@0 188
paulo@0 189 /*****************************************************************************/
paulo@0 190
paulo@0 191 #if 0
paulo@0 192 static int print_node (struct cached_node *node, String *s)
paulo@0 193 {
paulo@0 194 char *src;
paulo@0 195
paulo@0 196 src = STRDUP (net_ip_str (node->src_ip));
paulo@0 197
paulo@0 198 string_appendf (s, "[%s:%hu {%s}] ", net_ip_str (node->addr.ip),
paulo@0 199 node->addr.port, src);
paulo@0 200 free (src);
paulo@0 201
paulo@0 202 return FALSE;
paulo@0 203 }
paulo@0 204
paulo@0 205 static void print_list (char *prefix, List *list)
paulo@0 206 {
paulo@0 207 String *s;
paulo@0 208
paulo@0 209 if (!(s = string_new (NULL, 0, 0, TRUE)))
paulo@0 210 return;
paulo@0 211
paulo@0 212 string_append (s, prefix);
paulo@0 213
paulo@0 214 list_foreach (list, (ListForeachFunc)print_node, s);
paulo@0 215 GT->dbg (GT, "%s", s->str);
paulo@0 216
paulo@0 217 string_free (s);
paulo@0 218 }
paulo@0 219 #endif
paulo@0 220
paulo@0 221 void gt_node_cache_trace (void)
paulo@0 222 {
paulo@0 223 #if 0
paulo@0 224 print_list ("recent: ", recent);
paulo@0 225 print_list ("stable: ", stable);
paulo@0 226 print_list ("sticky_recent: ", sticky_recent);
paulo@0 227 print_list ("sticky_stable: ", sticky_stable);
paulo@0 228 #endif
paulo@0 229 }
paulo@0 230
paulo@0 231 /*****************************************************************************/
paulo@0 232
paulo@0 233 /* return some nodes from the cache, and remove them */
paulo@0 234 size_t get_first (List **src_list, List **dst_list, size_t nr)
paulo@0 235 {
paulo@0 236 struct cached_node *node;
paulo@0 237 struct cached_node *dup;
paulo@0 238
paulo@0 239 node = list_nth_data (*src_list, 0);
paulo@0 240
paulo@0 241 if (!node || !(dup = gift_memdup (node, sizeof (*node))))
paulo@0 242 return nr;
paulo@0 243
paulo@0 244 *dst_list = list_prepend (*dst_list, dup);
paulo@0 245 nr--;
paulo@0 246
paulo@0 247 gt_node_cache_del_ipv4 (node->addr.ip, node->addr.port);
paulo@0 248 return nr;
paulo@0 249 }
paulo@0 250
paulo@0 251 /*
paulo@0 252 * Remove some elements from the cache and return them in a list .
paulo@0 253 *
paulo@0 254 * The nodes and the list returned SHOULD be freed.
paulo@0 255 */
paulo@0 256 List *gt_node_cache_get_remove (size_t nr)
paulo@0 257 {
paulo@0 258 List *list = NULL;
paulo@0 259
paulo@0 260 /*
paulo@0 261 * We check the recent list first, and then if that's empty check the
paulo@0 262 * stable list, so we don't end up checking the stable list all the time.
paulo@0 263 */
paulo@0 264 while (nr > 0 && recent != NULL)
paulo@0 265 nr = get_first (&recent, &list, nr);
paulo@0 266
paulo@0 267 while (nr > 0 && stable != NULL)
paulo@0 268 nr = get_first (&stable, &list, nr);
paulo@0 269
paulo@0 270 return list;
paulo@0 271 }
paulo@0 272
paulo@0 273 /*
paulo@0 274 * Return some elements from the cache in a list
paulo@0 275 *
paulo@0 276 * NOTE: the data in the list returned SHOULD NOT be freed
paulo@0 277 */
paulo@0 278 List *gt_node_cache_get (size_t nr)
paulo@0 279 {
paulo@0 280 List *list = NULL;
paulo@0 281 size_t len;
paulo@0 282 int index;
paulo@0 283
paulo@0 284 len = list_length (sticky_recent);
paulo@0 285
paulo@0 286 /*
paulo@0 287 * If we don't have more than twice the number of nodes, just return an
paulo@0 288 * offset in the list of recent nodes.
paulo@0 289 *
paulo@0 290 * This is done so we can use the simple (stupid) selection algorithm
paulo@0 291 * below that would be inefficient otherwise.
paulo@0 292 */
paulo@0 293 if (len / 2 < nr)
paulo@0 294 return list_copy (list_nth (sticky_recent, MAX (0, len - nr)));
paulo@0 295
paulo@0 296 while (nr > 0)
paulo@0 297 {
paulo@0 298 struct cached_node *node;
paulo@0 299
paulo@0 300 index = (float)len * rand() / (RAND_MAX + 1.0);
paulo@0 301
paulo@0 302 node = list_nth_data (sticky_recent, index);
paulo@0 303 assert (node != NULL);
paulo@0 304
paulo@0 305 if (list_find (list, node))
paulo@0 306 continue;
paulo@0 307
paulo@0 308 list = list_append (list, node);
paulo@0 309 nr--;
paulo@0 310 }
paulo@0 311
paulo@0 312 return list;
paulo@0 313 }
paulo@0 314
paulo@0 315 /*****************************************************************************/
paulo@0 316
paulo@0 317 static char *node_cache_file (const char *name)
paulo@0 318 {
paulo@0 319 return gift_conf_path ("Gnutella/%s", name);
paulo@0 320 }
paulo@0 321
paulo@0 322 /*
paulo@0 323 * Store the cache data in the dataset. The ip:port as a string
paulo@0 324 * is used as a key.
paulo@0 325 */
paulo@0 326 static BOOL write_line (struct cached_node *node, FileCache *cache)
paulo@0 327 {
paulo@0 328 char *ip_port;
paulo@0 329 char *line;
paulo@0 330
paulo@0 331 ip_port = stringf_dup ("%s:%hu", net_ip_str (node->addr.ip),
paulo@0 332 node->addr.port);
paulo@0 333
paulo@0 334 if (!ip_port)
paulo@0 335 return FALSE;
paulo@0 336
paulo@0 337 line = stringf_dup ("%s %lu %lu %s", gt_node_class_str (node->klass),
paulo@0 338 (long)node->timestamp, (long)node->uptime,
paulo@0 339 net_ip_str (node->src_ip));
paulo@0 340
paulo@0 341 if (!line)
paulo@0 342 {
paulo@0 343 free (ip_port);
paulo@0 344 return FALSE;
paulo@0 345 }
paulo@0 346
paulo@0 347 file_cache_insert (cache, ip_port, line);
paulo@0 348
paulo@0 349 free (ip_port);
paulo@0 350 free (line);
paulo@0 351
paulo@0 352 return FALSE;
paulo@0 353 }
paulo@0 354
paulo@0 355 /*
paulo@0 356 * Read in a line from a cache file.
paulo@0 357 *
paulo@0 358 * The ip:port is the key in the Dataset. The value
paulo@0 359 * is everything else that dsecribe an entry in the node
paulo@0 360 * cache, as a string.
paulo@0 361 */
paulo@0 362 static void parse_line (ds_data_t *key, ds_data_t *value, void *udata)
paulo@0 363 {
paulo@0 364 char *ip_port = key->data;
paulo@0 365 char *str = value->data;
paulo@0 366 in_addr_t ipv4;
paulo@0 367 in_port_t port;
paulo@0 368 time_t timestamp;
paulo@0 369 time_t uptime;
paulo@0 370 in_addr_t src_ip;
paulo@0 371 char *klass;
paulo@0 372
paulo@0 373 ipv4 = net_ip (string_sep (&ip_port, ":"));
paulo@0 374 port = ATOUL (ip_port);
paulo@0 375
paulo@0 376 if (ipv4 == 0 || ipv4 == INADDR_NONE || port == 0)
paulo@0 377 return;
paulo@0 378
paulo@0 379 /* NOTE: we ignore the class string for now */
paulo@0 380 klass = string_sep (&str, " ");
paulo@0 381 timestamp = ATOUL (string_sep (&str, " "));
paulo@0 382 uptime = ATOUL (string_sep (&str, " "));
paulo@0 383 src_ip = net_ip (string_sep (&str, " "));
paulo@0 384
paulo@0 385 if (!klass || timestamp == 0)
paulo@0 386 return;
paulo@0 387
paulo@0 388 /* add it to the cache */
paulo@0 389 gt_node_cache_add_ipv4 (ipv4, port, GT_NODE_ULTRA, timestamp, uptime,
paulo@0 390 src_ip);
paulo@0 391 }
paulo@0 392
paulo@0 393 static BOOL load_cache (char *name)
paulo@0 394 {
paulo@0 395 FileCache *cache;
paulo@0 396 char *file;
paulo@0 397
paulo@0 398 file = node_cache_file (name);
paulo@0 399 cache = file_cache_new (file);
paulo@0 400
paulo@0 401 if (!cache)
paulo@0 402 return FALSE;
paulo@0 403
paulo@0 404 dataset_foreach (cache->d, DS_FOREACH(parse_line), NULL);
paulo@0 405
paulo@0 406 file_cache_free (cache);
paulo@0 407 return TRUE;
paulo@0 408 }
paulo@0 409
paulo@0 410 static BOOL save_cache (char *name, List *list)
paulo@0 411 {
paulo@0 412 FileCache *cache;
paulo@0 413 char *file;
paulo@0 414
paulo@0 415 file = node_cache_file (name);
paulo@0 416 cache = file_cache_new (file);
paulo@0 417
paulo@0 418 /* flush the existing data (in memory, only) */
paulo@0 419 file_cache_flush (cache);
paulo@0 420
paulo@0 421 /* save each entry in the node cache to the file cache */
paulo@0 422 list_foreach (list, (ListForeachFunc)write_line, cache);
paulo@0 423
paulo@0 424 if (!file_cache_sync (cache))
paulo@0 425 {
paulo@0 426 GT->DBGFN (GT, "error saving cache \"%s\": %s", name, GIFT_STRERROR());
paulo@0 427 return FALSE;
paulo@0 428 }
paulo@0 429
paulo@0 430 file_cache_free (cache);
paulo@0 431
paulo@0 432 return TRUE;
paulo@0 433 }
paulo@0 434
paulo@0 435 void gt_node_cache_load (void)
paulo@0 436 {
paulo@0 437 load_cache ("stable_nodes");
paulo@0 438 load_cache ("recent_nodes");
paulo@0 439 }
paulo@0 440
paulo@0 441 void gt_node_cache_save (void)
paulo@0 442 {
paulo@0 443 save_cache ("stable_nodes", sticky_stable);
paulo@0 444 save_cache ("recent_nodes", sticky_recent);
paulo@0 445 }
paulo@0 446
paulo@0 447 /*****************************************************************************/
paulo@0 448
paulo@0 449 void gt_node_cache_init (void)
paulo@0 450 {
paulo@0 451 gt_node_cache_load ();
paulo@0 452 }
paulo@0 453
paulo@0 454 void gt_node_cache_cleanup (void)
paulo@0 455 {
paulo@0 456 gt_node_cache_save ();
paulo@0 457
paulo@0 458 /* TODO: free node cache lists */
paulo@0 459 }