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

annotate src/gt_node_list.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_list.c,v 1.12 2004/01/29 07:50:25 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_list.h"
paulo@0 21
paulo@0 22 /*
paulo@0 23 * TODO: rename gt_conn -> gt_node_list
paulo@0 24 */
paulo@0 25
paulo@0 26 /*****************************************************************************/
paulo@0 27
paulo@0 28 /* list of all nodes -- NOTE: duplicated info in gt_node.c */
paulo@0 29 static List *node_list;
paulo@0 30
paulo@0 31 /* last place in node_list for gt_conn_foreach */
paulo@0 32 static List *iterator;
paulo@0 33
paulo@0 34 /* cache of length of connected portion of node list by class (GtNodeLeaf,
paulo@0 35 * first, then GtNodeUltra) */
paulo@0 36 static int len_cache[2] = { 0 };
paulo@0 37
paulo@0 38 /*****************************************************************************/
paulo@0 39
paulo@0 40 static void move_iterator (GtNode *mv)
paulo@0 41 {
paulo@0 42 if (list_nth_data (iterator, 0) == mv)
paulo@0 43 iterator = list_next (iterator);
paulo@0 44 }
paulo@0 45
paulo@0 46 void gt_conn_add (GtNode *node)
paulo@0 47 {
paulo@0 48 if (!node)
paulo@0 49 {
paulo@0 50 GIFT_ERROR (("adding null node to node list"));
paulo@0 51 return;
paulo@0 52 }
paulo@0 53
paulo@0 54 node_list = list_append (node_list, node);
paulo@0 55 }
paulo@0 56
paulo@0 57 void gt_conn_remove (GtNode *node)
paulo@0 58 {
paulo@0 59 if (!list_find (node_list, node))
paulo@0 60 return;
paulo@0 61
paulo@0 62 /* move the iterator if it's pointing at the node we're removing */
paulo@0 63 move_iterator (node);
paulo@0 64
paulo@0 65 node_list = list_remove (node_list, node);
paulo@0 66 }
paulo@0 67
paulo@0 68 static void trace_list (List *nodes)
paulo@0 69 {
paulo@0 70 GtNode *node;
paulo@0 71
paulo@0 72 if (!nodes)
paulo@0 73 return;
paulo@0 74
paulo@0 75 node = list_nth_data (nodes, 0);
paulo@0 76
paulo@0 77 assert (node != NULL);
paulo@0 78 assert (GT_CONN(node) != NULL);
paulo@0 79
paulo@0 80 GT->DBGFN (GT, "%s:%hu", net_ip_str (node->ip), node->gt_port);
paulo@0 81
paulo@0 82 if (list_next (nodes))
paulo@0 83 trace_list (list_next (nodes));
paulo@0 84 }
paulo@0 85
paulo@0 86 /*****************************************************************************/
paulo@0 87
paulo@0 88 GtNode *gt_conn_foreach (GtConnForeachFunc func, void *udata,
paulo@0 89 gt_node_class_t klass, gt_node_state_t state,
paulo@0 90 int iter)
paulo@0 91 {
paulo@0 92 GtNode *node;
paulo@0 93 TCPC *c;
paulo@0 94 GtNode *ret = NULL;
paulo@0 95 List *ptr;
paulo@0 96 List *start;
paulo@0 97 List *next;
paulo@0 98 unsigned int i, count;
paulo@0 99 int looped = FALSE;
paulo@0 100 int iterating = FALSE;
paulo@0 101
paulo@0 102 assert (func != NULL);
paulo@0 103
paulo@0 104 #if 0
paulo@0 105 GT->DBGFN (GT, "length of conn list: %u", list_length (connections));
paulo@0 106 #endif
paulo@0 107
paulo@0 108 if (iter)
paulo@0 109 iterating = TRUE;
paulo@0 110
paulo@0 111 if (!iterator)
paulo@0 112 iterator = node_list;
paulo@0 113
paulo@0 114 start = ptr = (iterating) ? iterator : node_list;
paulo@0 115
paulo@0 116 /* having count be the static list length should keep
paulo@0 117 * concurrent conn_adds from making us never stop */
paulo@0 118 count = list_length (node_list);
paulo@0 119
paulo@0 120 /* hack for backward-compatible interface */
paulo@0 121 if (state == (gt_node_state_t) -1)
paulo@0 122 state = GT_NODE_ANY;
paulo@0 123
paulo@0 124 for (i = 0; i < count; i++)
paulo@0 125 {
paulo@0 126 if (iter && !ptr && !looped)
paulo@0 127 {
paulo@0 128 /* data only gets appended to connection list:
paulo@0 129 * safe to use head of connection list (connections) */
paulo@0 130 ptr = node_list;
paulo@0 131 looped = TRUE;
paulo@0 132 }
paulo@0 133
paulo@0 134 if (!ptr)
paulo@0 135 break;
paulo@0 136
paulo@0 137 /* we wrapped to the beginning, but have just reached the original
paulo@0 138 * start so we should bail out */
paulo@0 139 if (looped && ptr == start)
paulo@0 140 break;
paulo@0 141
paulo@0 142 node = ptr->data;
paulo@0 143 c = GT_CONN(node);
paulo@0 144
paulo@0 145 assert (node != NULL);
paulo@0 146
paulo@0 147 if (klass && !(node->klass & klass))
paulo@0 148 {
paulo@0 149 ptr = list_next (ptr);
paulo@0 150 continue;
paulo@0 151 }
paulo@0 152
paulo@0 153 if (state != GT_NODE_ANY && node->state != state)
paulo@0 154 {
paulo@0 155 ptr = list_next (ptr);
paulo@0 156 continue;
paulo@0 157 }
paulo@0 158
paulo@0 159 /* grab the next item. this allows the callback to free this item */
paulo@0 160 next = list_next (ptr);
paulo@0 161
paulo@0 162 ret = (*func) (c, node, udata);
paulo@0 163
paulo@0 164 ptr = next;
paulo@0 165
paulo@0 166 if (ret)
paulo@0 167 break;
paulo@0 168
paulo@0 169 if (iterating && --iter == 0)
paulo@0 170 break;
paulo@0 171 }
paulo@0 172
paulo@0 173 /* save the position for next time */
paulo@0 174 if (iterating)
paulo@0 175 iterator = ptr;
paulo@0 176
paulo@0 177 return ret;
paulo@0 178 }
paulo@0 179
paulo@0 180 /*****************************************************************************/
paulo@0 181
paulo@0 182 static void add_connected (gt_node_class_t klass)
paulo@0 183 {
paulo@0 184 int add;
paulo@0 185
paulo@0 186 if (klass != GT_NODE_LEAF && klass != GT_NODE_ULTRA)
paulo@0 187 return;
paulo@0 188
paulo@0 189 add = (klass == GT_NODE_LEAF ? 0 : 1);
paulo@0 190 len_cache[add]++;
paulo@0 191 }
paulo@0 192
paulo@0 193 static void del_connected (gt_node_class_t klass)
paulo@0 194 {
paulo@0 195 int del;
paulo@0 196
paulo@0 197 if (klass != GT_NODE_LEAF && klass != GT_NODE_ULTRA)
paulo@0 198 return;
paulo@0 199
paulo@0 200 del = (klass == GT_NODE_LEAF ? 0 : 1);
paulo@0 201 len_cache[del]--;
paulo@0 202 }
paulo@0 203
paulo@0 204 void gt_conn_set_state (GtNode *node, gt_node_state_t old_state,
paulo@0 205 gt_node_state_t new_state)
paulo@0 206 {
paulo@0 207 if (new_state == GT_NODE_CONNECTED && old_state != GT_NODE_CONNECTED)
paulo@0 208 add_connected (node->klass);
paulo@0 209
paulo@0 210 if (new_state != GT_NODE_CONNECTED && old_state == GT_NODE_CONNECTED)
paulo@0 211 del_connected (node->klass);
paulo@0 212 }
paulo@0 213
paulo@0 214 void gt_conn_set_class (GtNode *node, gt_node_class_t old_class,
paulo@0 215 gt_node_class_t new_class)
paulo@0 216 {
paulo@0 217 if (node->state != GT_NODE_CONNECTED)
paulo@0 218 return;
paulo@0 219
paulo@0 220 del_connected (old_class);
paulo@0 221 add_connected (new_class);
paulo@0 222
paulo@0 223 assert (len_cache[0] >= 0);
paulo@0 224 assert (len_cache[1] >= 0);
paulo@0 225 }
paulo@0 226
paulo@0 227 static int check_len_cache (gt_node_class_t klass)
paulo@0 228 {
paulo@0 229 int len = 0;
paulo@0 230
paulo@0 231 if (klass == GT_NODE_NONE)
paulo@0 232 klass = GT_NODE_LEAF | GT_NODE_ULTRA;
paulo@0 233
paulo@0 234 if (klass & GT_NODE_LEAF)
paulo@0 235 len += len_cache[0];
paulo@0 236
paulo@0 237 if (klass & GT_NODE_ULTRA)
paulo@0 238 len += len_cache[1];
paulo@0 239
paulo@0 240 return len;
paulo@0 241 }
paulo@0 242
paulo@0 243 static GtNode *conn_counter (TCPC *c, GtNode *node, int *length)
paulo@0 244 {
paulo@0 245 (*length)++;
paulo@0 246 return NULL;
paulo@0 247 }
paulo@0 248
paulo@0 249 int gt_conn_length (gt_node_class_t klass, gt_node_state_t state)
paulo@0 250 {
paulo@0 251 int ret = 0;
paulo@0 252 int cached_len;
paulo@0 253
paulo@0 254 /*
paulo@0 255 * We keep a small cache of the length of connected ultrapeers+leaves
paulo@0 256 * so we don't have to traverse the list most of the time here.
paulo@0 257 *
paulo@0 258 * Traversal still happens now as a sanity check.
paulo@0 259 */
paulo@0 260 if (state == GT_NODE_CONNECTED &&
paulo@0 261 (klass == GT_NODE_NONE || klass == GT_NODE_LEAF ||
paulo@0 262 klass == GT_NODE_ULTRA))
paulo@0 263 {
paulo@0 264 cached_len = check_len_cache (klass);
paulo@0 265
paulo@0 266 /* make sure the cache length is the same as the real one */
paulo@0 267 gt_conn_foreach (GT_CONN_FOREACH(conn_counter), &ret, klass, state, 0);
paulo@0 268 assert (ret == cached_len);
paulo@0 269
paulo@0 270 return cached_len;
paulo@0 271 }
paulo@0 272
paulo@0 273 gt_conn_foreach (GT_CONN_FOREACH(conn_counter), &ret,
paulo@0 274 klass, state, 0);
paulo@0 275
paulo@0 276 return ret;
paulo@0 277 }
paulo@0 278
paulo@0 279 /*****************************************************************************/
paulo@0 280
paulo@0 281 static GtNode *select_rand (TCPC *c, GtNode *node, void **cmp)
paulo@0 282 {
paulo@0 283 int *nr = cmp[0];
paulo@0 284 GtNode **ret = cmp[1];
paulo@0 285 float range = *nr;
paulo@0 286 float prob;
paulo@0 287
paulo@0 288 /* make sure we pick at least one */
paulo@0 289 if (!*ret)
paulo@0 290 *ret = node;
paulo@0 291
paulo@0 292 /* set the probability of selecting this node */
paulo@0 293 prob = range * rand() / (RAND_MAX + 1.0);
paulo@0 294
paulo@0 295 if (prob < 1)
paulo@0 296 *ret = node;
paulo@0 297
paulo@0 298 (*nr)++;
paulo@0 299
paulo@0 300 /* we dont use the return value here, because we need to try
paulo@0 301 * all the nodes, and returning non-null here short-circuits */
paulo@0 302 return NULL;
paulo@0 303 }
paulo@0 304
paulo@0 305 /*
paulo@0 306 * Pick a node at random that is also of the specified
paulo@0 307 * class and state.
paulo@0 308 */
paulo@0 309 GtNode *gt_conn_random (gt_node_class_t klass, gt_node_state_t state)
paulo@0 310 {
paulo@0 311 void *cmp[2];
paulo@0 312 int nr;
paulo@0 313 GtNode *ret = NULL;
paulo@0 314
paulo@0 315 /* initial probability */
paulo@0 316 nr = 1;
paulo@0 317
paulo@0 318 cmp[0] = &nr;
paulo@0 319 cmp[1] = &ret;
paulo@0 320
paulo@0 321 gt_conn_foreach (GT_CONN_FOREACH(select_rand), cmp,
paulo@0 322 klass, state, 0);
paulo@0 323
paulo@0 324 return ret;
paulo@0 325 }
paulo@0 326
paulo@0 327 /*****************************************************************************/
paulo@0 328
paulo@0 329 static BOOL collect_old (GtNode *node, void **data)
paulo@0 330 {
paulo@0 331 List **to_free = data[0];
paulo@0 332 int *max_tofree = data[1];
paulo@0 333
paulo@0 334 /* don't make the node list too small */
paulo@0 335 if (*max_tofree == 0)
paulo@0 336 return FALSE;
paulo@0 337
paulo@0 338 if (gt_node_freeable (node))
paulo@0 339 {
paulo@0 340 /* protect the iterator because we're removing a node */
paulo@0 341 move_iterator (node);
paulo@0 342
paulo@0 343 (*max_tofree)--;
paulo@0 344 *to_free = list_append (*to_free, node);
paulo@0 345
paulo@0 346 return TRUE;
paulo@0 347 }
paulo@0 348
paulo@0 349 return FALSE;
paulo@0 350 }
paulo@0 351
paulo@0 352 static BOOL dump_node (GtNode *node, void *udata)
paulo@0 353 {
paulo@0 354 gt_node_free (node);
paulo@0 355 return TRUE;
paulo@0 356 }
paulo@0 357
paulo@0 358 /*
paulo@0 359 * NOTE: We can't re-descend the node_list by calling gt_node_free [which
paulo@0 360 * calls gt_conn_remove->list_remove] while iterating the node_list in
paulo@0 361 * list_foreach_remove. So, we build a second a list of nodes to free while
paulo@0 362 * removing those from node_list "by hand" and then free that list.
paulo@0 363 */
paulo@0 364 void gt_conn_trim (void)
paulo@0 365 {
paulo@0 366 List *to_free = NULL;
paulo@0 367 int max_tofree;
paulo@0 368 int len;
paulo@0 369 void *data[2];
paulo@0 370
paulo@0 371 len = list_length (node_list);
paulo@0 372 max_tofree = MAX (0, len - 500);
paulo@0 373
paulo@0 374 data[0] = &to_free;
paulo@0 375 data[1] = &max_tofree;
paulo@0 376
paulo@0 377 /* get rid of the oldest nodes first */
paulo@0 378 gt_conn_sort ((CompareFunc)gt_conn_sort_vit_neg);
paulo@0 379
paulo@0 380 node_list = list_foreach_remove (node_list, (ListForeachFunc)collect_old,
paulo@0 381 data);
paulo@0 382
paulo@0 383 GT->DBGFN (GT, "trimming %d/%d nodes", list_length (to_free), len);
paulo@0 384 list_foreach_remove (to_free, (ListForeachFunc)dump_node, NULL);
paulo@0 385
paulo@0 386 /* set the node list back to rights wrt vitality */
paulo@0 387 gt_conn_sort ((CompareFunc)gt_conn_sort_vit);
paulo@0 388
paulo@0 389 /* reset the iterator to some random node */
paulo@0 390 iterator = list_nth (node_list,
paulo@0 391 (float)rand() * len / (RAND_MAX + 1.0));
paulo@0 392 }
paulo@0 393
paulo@0 394 /*****************************************************************************/
paulo@0 395
paulo@0 396 int gt_conn_sort_vit (GtNode *a, GtNode *b)
paulo@0 397 {
paulo@0 398 if (a->vitality > b->vitality)
paulo@0 399 return -1;
paulo@0 400 else if (a->vitality < b->vitality)
paulo@0 401 return 1;
paulo@0 402 else
paulo@0 403 return 0;
paulo@0 404 }
paulo@0 405
paulo@0 406 int gt_conn_sort_vit_neg (GtNode *a, GtNode *b)
paulo@0 407 {
paulo@0 408 return -gt_conn_sort_vit (a, b);
paulo@0 409 }
paulo@0 410
paulo@0 411 /* NOTE: this isnt safe to call at all times */
paulo@0 412 void gt_conn_sort (CompareFunc func)
paulo@0 413 {
paulo@0 414 node_list = list_sort (node_list, func);
paulo@0 415
paulo@0 416 /* reset the iterator */
paulo@0 417 iterator = NULL;
paulo@0 418 }
paulo@0 419
paulo@0 420 /*****************************************************************************/
paulo@0 421
paulo@0 422 struct _sync_args
paulo@0 423 {
paulo@0 424 time_t tm;
paulo@0 425 FILE *f;
paulo@0 426 };
paulo@0 427
paulo@0 428 static GtNode *sync_node (TCPC *c, GtNode *node, struct _sync_args *sync)
paulo@0 429 {
paulo@0 430 size_t ret;
paulo@0 431
paulo@0 432 /* node->vitality is updated lazily, to avoid a syscall for every
paulo@0 433 * packet. Maybe this isnt worth it */
paulo@0 434 if (node->state & GT_NODE_CONNECTED)
paulo@0 435 node->vitality = sync->tm;
paulo@0 436
paulo@0 437 /* only cache the node if we have connected to it before successfully */
paulo@0 438 if (node->vitality > 0 &&
paulo@0 439 node->gt_port > 0)
paulo@0 440 {
paulo@0 441 ret = fprintf (sync->f, "%lu %s:%hu %lu %lu\n", (long)node->vitality,
paulo@0 442 net_ip_str (node->ip), node->gt_port,
paulo@0 443 (long)node->size_kb, (long)node->files);
paulo@0 444
paulo@0 445 /* stop iterating if there was an error */
paulo@0 446 if (ret <= 0)
paulo@0 447 return node;
paulo@0 448 }
paulo@0 449
paulo@0 450 return NULL;
paulo@0 451 }
paulo@0 452
paulo@0 453 void gt_node_list_save (void)
paulo@0 454 {
paulo@0 455 struct _sync_args sync;
paulo@0 456 char *tmp_path;
paulo@0 457
paulo@0 458 time (&sync.tm);
paulo@0 459 tmp_path = STRDUP (gift_conf_path ("Gnutella/nodes.tmp"));
paulo@0 460
paulo@0 461 if (!(sync.f = fopen (gift_conf_path ("Gnutella/nodes.tmp"), "w")))
paulo@0 462 {
paulo@0 463 GT->DBGFN (GT, "error opening tmp file: %s", GIFT_STRERROR ());
paulo@0 464 free (tmp_path);
paulo@0 465 return;
paulo@0 466 }
paulo@0 467
paulo@0 468 /*
paulo@0 469 * The nodes file is fairly important. Check for errors when writing to
paulo@0 470 * the disk.
paulo@0 471 */
paulo@0 472 if (gt_conn_foreach (GT_CONN_FOREACH(sync_node), &sync,
paulo@0 473 GT_NODE_NONE, GT_NODE_ANY, 0) != NULL)
paulo@0 474 {
paulo@0 475 GT->warn (GT, "error writing nodes file: %s", GIFT_STRERROR());
paulo@0 476 fclose (sync.f);
paulo@0 477 free (tmp_path);
paulo@0 478 return;
paulo@0 479 }
paulo@0 480
paulo@0 481 if (fclose (sync.f) != 0)
paulo@0 482 {
paulo@0 483 GT->warn (GT, "error closing nodes file: %s", GIFT_STRERROR());
paulo@0 484 free (tmp_path);
paulo@0 485 return;
paulo@0 486 }
paulo@0 487
paulo@0 488 file_mv (tmp_path, gift_conf_path ("Gnutella/nodes"));
paulo@0 489
paulo@0 490 free (tmp_path);
paulo@0 491 }
paulo@0 492
paulo@0 493 static void load_nodes (/*const*/ char *conf_path, gt_node_class_t klass)
paulo@0 494 {
paulo@0 495 GtNode *node;
paulo@0 496 FILE *f;
paulo@0 497 char *buf = NULL;
paulo@0 498 char *ptr;
paulo@0 499
paulo@0 500 f = fopen (gift_conf_path (conf_path), "r");
paulo@0 501
paulo@0 502 /* try the global nodes file */
paulo@0 503 if (!f)
paulo@0 504 {
paulo@0 505 char *filename;
paulo@0 506
paulo@0 507 if (!(filename = malloc (strlen (platform_data_dir ()) + 50)))
paulo@0 508 return;
paulo@0 509
paulo@0 510 sprintf (filename, "%s/%s", platform_data_dir (), conf_path);
paulo@0 511
paulo@0 512 f = fopen (filename, "r");
paulo@0 513
paulo@0 514 free (filename);
paulo@0 515 }
paulo@0 516
paulo@0 517 if (!f)
paulo@0 518 return;
paulo@0 519
paulo@0 520 while (file_read_line (f, &buf))
paulo@0 521 {
paulo@0 522 unsigned long vitality;
paulo@0 523 in_addr_t ip;
paulo@0 524 in_port_t port;
paulo@0 525 uint32_t size_kb;
paulo@0 526 uint32_t files;
paulo@0 527
paulo@0 528 ptr = buf;
paulo@0 529
paulo@0 530 /* [vitality] [ip]:[port] [shares size(kB)] [file count] */
paulo@0 531
paulo@0 532 vitality = ATOUL (string_sep (&ptr, " "));
paulo@0 533 ip = net_ip (string_sep (&ptr, ":"));
paulo@0 534 port = ATOI (string_sep (&ptr, " "));
paulo@0 535 size_kb = ATOI (string_sep (&ptr, " "));
paulo@0 536 files = ATOI (string_sep (&ptr, " "));
paulo@0 537
paulo@0 538 if (!ip || ip == INADDR_NONE)
paulo@0 539 continue;
paulo@0 540
paulo@0 541 if (size_kb == (uint32_t)-1)
paulo@0 542 size_kb = 0;
paulo@0 543
paulo@0 544 if (files == (uint32_t)-1)
paulo@0 545 files = 0;
paulo@0 546
paulo@0 547 node = gt_node_register (ip, port, klass);
paulo@0 548
paulo@0 549 if (!node)
paulo@0 550 continue;
paulo@0 551
paulo@0 552 node->vitality = vitality;
paulo@0 553
paulo@0 554 node->size_kb = size_kb;
paulo@0 555 node->files = files;
paulo@0 556 }
paulo@0 557
paulo@0 558 fclose (f);
paulo@0 559 }
paulo@0 560
paulo@0 561 void gt_node_list_load (void)
paulo@0 562 {
paulo@0 563 load_nodes ("Gnutella/nodes", GT_NODE_ULTRA);
paulo@0 564
paulo@0 565 /* sort the list so we contact the most recent nodes first */
paulo@0 566 gt_conn_sort ((CompareFunc) gt_conn_sort_vit);
paulo@0 567 }