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

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