diff options
author | Christian Grothoff <christian@grothoff.org> | 2011-09-26 22:02:03 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2011-09-26 22:02:03 +0000 |
commit | 1f6511d450641f20c69f616dbdbbbb1badbbbc5a (patch) | |
tree | ee31851b7eb5de4e6251c2e4a0d488fb886f8b12 /src/dht/gnunet-service-dht_routing.c | |
parent | b77a243b51a385d52250d31a285669b7ad3aed20 (diff) | |
download | gnunet-1f6511d450641f20c69f616dbdbbbb1badbbbc5a.tar.gz gnunet-1f6511d450641f20c69f616dbdbbbb1badbbbc5a.zip |
more wild hxing
Diffstat (limited to 'src/dht/gnunet-service-dht_routing.c')
-rw-r--r-- | src/dht/gnunet-service-dht_routing.c | 211 |
1 files changed, 211 insertions, 0 deletions
diff --git a/src/dht/gnunet-service-dht_routing.c b/src/dht/gnunet-service-dht_routing.c new file mode 100644 index 000000000..535a63267 --- /dev/null +++ b/src/dht/gnunet-service-dht_routing.c | |||
@@ -0,0 +1,211 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet. | ||
3 | (C) 2011 Christian Grothoff (and other contributing authors) | ||
4 | |||
5 | GNUnet is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published | ||
7 | by the Free Software Foundation; either version 3, or (at your | ||
8 | option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with GNUnet; see the file COPYING. If not, write to the | ||
17 | Free Software Foundation, Inc., 59 Temple Place - Suite 330, | ||
18 | Boston, MA 02111-1307, USA. | ||
19 | */ | ||
20 | |||
21 | /** | ||
22 | * @file dht/gnunet-service-dht_routing.c | ||
23 | * @brief GNUnet DHT tracking of requests for routing replies | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | |||
27 | #include "gnunet-service-dht_routing.h" | ||
28 | |||
29 | |||
30 | /** | ||
31 | * Number of requests we track at most (for routing replies). | ||
32 | */ | ||
33 | #define DHT_MAX_RECENT (1024 * 16) | ||
34 | |||
35 | |||
36 | /** | ||
37 | * Information we keep about all recent GET requests | ||
38 | * so that we can route replies. | ||
39 | */ | ||
40 | struct RecentRequest | ||
41 | { | ||
42 | |||
43 | /** | ||
44 | * The peer this request was received from. | ||
45 | */ | ||
46 | struct GNUNET_PeerIdentity peer; | ||
47 | |||
48 | /** | ||
49 | * Position of this node in the min heap. | ||
50 | */ | ||
51 | struct GNUNET_CONTAINER_HeapNode *heap_node; | ||
52 | |||
53 | /** | ||
54 | * Bloomfilter for replies to drop. | ||
55 | */ | ||
56 | struct GNUNET_CONTAINER_BloomFilter *reply_bf; | ||
57 | |||
58 | /** | ||
59 | * Timestamp of this request, for ordering | ||
60 | * the min heap. | ||
61 | */ | ||
62 | struct GNUNET_TIME_Absolute timestamp; | ||
63 | |||
64 | /** | ||
65 | * Type of the requested block. | ||
66 | */ | ||
67 | enum GNUNET_BLOCK_Type type; | ||
68 | |||
69 | /** | ||
70 | * extended query (see gnunet_block_lib.h). Allocated at the | ||
71 | * end of this struct. | ||
72 | */ | ||
73 | const void *xquery; | ||
74 | |||
75 | /** | ||
76 | * Number of bytes in xquery. | ||
77 | */ | ||
78 | size_t xquery_size; | ||
79 | |||
80 | /** | ||
81 | * Mutator value for the reply_bf, see gnunet_block_lib.h | ||
82 | */ | ||
83 | uint32_t reply_bf_mutator; | ||
84 | |||
85 | /** | ||
86 | * Key of this request. | ||
87 | */ | ||
88 | GNUNET_HashCode key; | ||
89 | |||
90 | }; | ||
91 | |||
92 | |||
93 | /** | ||
94 | * Recent requests by time inserted. | ||
95 | */ | ||
96 | static struct GNUNET_CONTAINER_Heap *recent_heap; | ||
97 | |||
98 | /** | ||
99 | * Recently seen requests by key. | ||
100 | */ | ||
101 | static struct GNUNET_CONTAINER_MultiHashMap *recent_map; | ||
102 | |||
103 | |||
104 | /** | ||
105 | * Handle a reply (route to origin). Only forwards the reply back to | ||
106 | * other peers waiting for it. Does not do local caching or | ||
107 | * forwarding to local clients. Essentially calls | ||
108 | * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching | ||
109 | * request recently. | ||
110 | * | ||
111 | * @param type type of the block | ||
112 | * @param expiration_time when does the content expire | ||
113 | * @param key key for the content | ||
114 | * @param put_path_length number of entries in put_path | ||
115 | * @param put_path peers the original PUT traversed (if tracked) | ||
116 | * @param get_path_length number of entries in put_path | ||
117 | * @param get_path peers this reply has traversed so far (if tracked) | ||
118 | * @param data payload of the reply | ||
119 | * @param data_size number of bytes in data | ||
120 | */ | ||
121 | void | ||
122 | GDS_ROUTING_process (enum GNUNET_BLOCK_Type type, | ||
123 | GNUNET_TIME_Absolute expiration_time, | ||
124 | const GNUNET_HashCode *key, | ||
125 | unsigned int put_path_length, | ||
126 | struct GNUNET_PeerIdentity *put_path, | ||
127 | unsigned int get_path_length, | ||
128 | struct GNUNET_PeerIdentity *get_path, | ||
129 | const void *data, | ||
130 | size_t data_size) | ||
131 | { | ||
132 | } | ||
133 | |||
134 | |||
135 | /** | ||
136 | * Add a new entry to our routing table. | ||
137 | * | ||
138 | * @param sender peer that originated the request | ||
139 | * @param type type of the block | ||
140 | * @param key key for the content | ||
141 | * @param xquery extended query | ||
142 | * @param xquery_size number of bytes in xquery | ||
143 | * @param reply_bf bloomfilter to filter duplicates | ||
144 | * @param reply_bf_mutator mutator for reply_bf | ||
145 | */ | ||
146 | void | ||
147 | GDS_ROUTING_add (const GNUNET_PeerIdentity *sender, | ||
148 | enum GNUNET_BLOCK_Type type, | ||
149 | const GNUNET_HashCode *key, | ||
150 | const void *xquery, | ||
151 | size_t xquery_size, | ||
152 | const struct GNUNET_CONTAINER_BloomFilter *reply_bf, | ||
153 | uint32_t reply_bf_mutator) | ||
154 | { | ||
155 | if (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT) | ||
156 | { | ||
157 | recent_req = GNUNET_CONTAINER_heap_peek (recent_heap); | ||
158 | GNUNET_assert (recent_req != NULL); | ||
159 | GNUNET_SCHEDULER_cancel (recent_req->remove_task); | ||
160 | GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node); | ||
161 | GNUNET_CONTAINER_bloomfilter_free (recent_req->bloom); | ||
162 | GNUNET_free (recent_req); | ||
163 | } | ||
164 | |||
165 | recent_req = GNUNET_malloc (sizeof (struct RecentRequest)); | ||
166 | recent_req->uid = msg_ctx->unique_id; | ||
167 | memcpy (&recent_req->key, &msg_ctx->key, sizeof (GNUNET_HashCode)); | ||
168 | recent_req->heap_node = | ||
169 | GNUNET_CONTAINER_heap_insert (recent_heap, recent_req, | ||
170 | GNUNET_TIME_absolute_get ().abs_value); | ||
171 | recent_req->bloom = | ||
172 | GNUNET_CONTAINER_bloomfilter_init (NULL, DHT_BLOOM_SIZE, DHT_BLOOM_K); | ||
173 | |||
174 | |||
175 | } | ||
176 | |||
177 | |||
178 | /** | ||
179 | * Initialize routing subsystem. | ||
180 | */ | ||
181 | void | ||
182 | GDS_ROUTING_init () | ||
183 | { | ||
184 | recent_heap = | ||
185 | GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); | ||
186 | recent_map = | ||
187 | GNUNET_CONTAINER_multihashmap_create (MAX_BUCKETS / 8); | ||
188 | } | ||
189 | |||
190 | |||
191 | /** | ||
192 | * Shutdown routing subsystem. | ||
193 | */ | ||
194 | void | ||
195 | GDS_ROUTING_done () | ||
196 | { | ||
197 | while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0) | ||
198 | { | ||
199 | recent_req = GNUNET_CONTAINER_heap_peek (recent_heap); | ||
200 | GNUNET_assert (recent_req != NULL); | ||
201 | GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node); | ||
202 | GNUNET_CONTAINER_bloomfilter_free (recent_req->bloom); | ||
203 | GNUNET_free (recent_req); | ||
204 | } | ||
205 | GNUNET_CONTAINER_heap_destroy (recent_heap); | ||
206 | recent_heap = NULL; | ||
207 | GNUNET_CONTAINER_multihashmap_destroy (recent_map); | ||
208 | recent_map = NULL; | ||
209 | } | ||
210 | |||
211 | /* end of gnunet-service-dht_routing.c */ | ||