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

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