diff options
Diffstat (limited to 'src/regex/regex_internal_dht.c')
-rw-r--r-- | src/regex/regex_internal_dht.c | 812 |
1 files changed, 812 insertions, 0 deletions
diff --git a/src/regex/regex_internal_dht.c b/src/regex/regex_internal_dht.c new file mode 100644 index 000000000..0b5d99928 --- /dev/null +++ b/src/regex/regex_internal_dht.c | |||
@@ -0,0 +1,812 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | (C) 2012 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 | * @file src/regex/regex_internal_dht.c | ||
22 | * @brief library to announce regexes in the network and match strings | ||
23 | * against published regexes. | ||
24 | * @author Bartlomiej Polot | ||
25 | */ | ||
26 | #include "platform.h" | ||
27 | #include "regex_internal_lib.h" | ||
28 | #include "regex_block_lib.h" | ||
29 | #include "gnunet_dht_service.h" | ||
30 | #include "gnunet_statistics_service.h" | ||
31 | |||
32 | #define LOG(kind,...) GNUNET_log_from (kind,"regex-dht",__VA_ARGS__) | ||
33 | |||
34 | /* FIXME: OPTION (API, CONFIG) */ | ||
35 | #define DHT_REPLICATION 5 | ||
36 | #define DHT_TTL GNUNET_TIME_UNIT_HOURS | ||
37 | #define DEBUG_DHT GNUNET_NO | ||
38 | |||
39 | #if DEBUG_DHT | ||
40 | #define DHT_OPT GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE | GNUNET_DHT_RO_RECORD_ROUTE | ||
41 | #else | ||
42 | #define DHT_OPT GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE | ||
43 | #endif | ||
44 | |||
45 | struct REGEX_ITERNAL_Announcement | ||
46 | { | ||
47 | /** | ||
48 | * DHT handle to use, must be initialized externally. | ||
49 | */ | ||
50 | struct GNUNET_DHT_Handle *dht; | ||
51 | |||
52 | /** | ||
53 | * Regular expression. | ||
54 | */ | ||
55 | const char *regex; | ||
56 | |||
57 | /** | ||
58 | * Automaton representation of the regex (expensive to build). | ||
59 | */ | ||
60 | struct REGEX_ITERNAL_Automaton* dfa; | ||
61 | |||
62 | /** | ||
63 | * Identity under which to announce the regex. | ||
64 | */ | ||
65 | struct GNUNET_PeerIdentity id; | ||
66 | |||
67 | /** | ||
68 | * Optional statistics handle to report usage. Can be NULL. | ||
69 | */ | ||
70 | struct GNUNET_STATISTICS_Handle *stats; | ||
71 | }; | ||
72 | |||
73 | |||
74 | /** | ||
75 | * Regex callback iterator to store own service description in the DHT. | ||
76 | * | ||
77 | * @param cls closure. | ||
78 | * @param key hash for current state. | ||
79 | * @param proof proof for current state. | ||
80 | * @param accepting GNUNET_YES if this is an accepting state, GNUNET_NO if not. | ||
81 | * @param num_edges number of edges leaving current state. | ||
82 | * @param edges edges leaving current state. | ||
83 | */ | ||
84 | static void | ||
85 | regex_iterator (void *cls, | ||
86 | const struct GNUNET_HashCode *key, | ||
87 | const char *proof, | ||
88 | int accepting, | ||
89 | unsigned int num_edges, | ||
90 | const struct REGEX_ITERNAL_Edge *edges) | ||
91 | { | ||
92 | struct REGEX_ITERNAL_Announcement *h = cls; | ||
93 | struct RegexBlock *block; | ||
94 | struct RegexEdge *block_edge; | ||
95 | size_t size; | ||
96 | size_t len; | ||
97 | unsigned int i; | ||
98 | unsigned int offset; | ||
99 | char *aux; | ||
100 | |||
101 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
102 | " regex dht put for state %s\n", | ||
103 | GNUNET_h2s (key)); | ||
104 | LOG (GNUNET_ERROR_TYPE_DEBUG, " proof: %s\n", proof); | ||
105 | LOG (GNUNET_ERROR_TYPE_DEBUG, " num edges: %u\n", num_edges); | ||
106 | |||
107 | if (GNUNET_YES == accepting) | ||
108 | { | ||
109 | struct RegexAccept block; | ||
110 | |||
111 | LOG (GNUNET_ERROR_TYPE_DEBUG, | ||
112 | " state %s is accepting, putting own id\n", | ||
113 | GNUNET_h2s(key)); | ||
114 | size = sizeof (block); | ||
115 | block.key = *key; | ||
116 | block.id = h->id; | ||
117 | GNUNET_STATISTICS_update (h->stats, "# regex accepting blocks stored", | ||
118 | 1, GNUNET_NO); | ||
119 | GNUNET_STATISTICS_update (h->stats, "# regex accepting block bytes stored", | ||
120 | sizeof (block), GNUNET_NO); | ||
121 | (void) | ||
122 | GNUNET_DHT_put (h->dht, key, | ||
123 | DHT_REPLICATION, | ||
124 | DHT_OPT | GNUNET_DHT_RO_RECORD_ROUTE, | ||
125 | GNUNET_BLOCK_TYPE_REGEX_ACCEPT, | ||
126 | size, | ||
127 | (char *) &block, | ||
128 | GNUNET_TIME_relative_to_absolute (DHT_TTL), | ||
129 | DHT_TTL, | ||
130 | NULL, NULL); | ||
131 | } | ||
132 | len = strlen(proof); | ||
133 | size = sizeof (struct RegexBlock) + len; | ||
134 | block = GNUNET_malloc (size); | ||
135 | |||
136 | block->key = *key; | ||
137 | block->n_proof = htonl (len); | ||
138 | block->n_edges = htonl (num_edges); | ||
139 | block->accepting = htonl (accepting); | ||
140 | |||
141 | /* Store the proof at the end of the block. */ | ||
142 | aux = (char *) &block[1]; | ||
143 | memcpy (aux, proof, len); | ||
144 | aux = &aux[len]; | ||
145 | |||
146 | /* Store each edge in a variable length MeshEdge struct at the | ||
147 | * very end of the MeshRegexBlock structure. | ||
148 | */ | ||
149 | for (i = 0; i < num_edges; i++) | ||
150 | { | ||
151 | LOG (GNUNET_ERROR_TYPE_DEBUG, " edge %s towards %s\n", | ||
152 | edges[i].label, GNUNET_h2s(&edges[i].destination)); | ||
153 | |||
154 | /* aux points at the end of the last block */ | ||
155 | len = strlen (edges[i].label); | ||
156 | size += sizeof (struct RegexEdge) + len; | ||
157 | // Calculate offset FIXME is this ok? use size instead? | ||
158 | offset = aux - (char *) block; | ||
159 | block = GNUNET_realloc (block, size); | ||
160 | aux = &((char *) block)[offset]; | ||
161 | block_edge = (struct RegexEdge *) aux; | ||
162 | block_edge->key = edges[i].destination; | ||
163 | block_edge->n_token = htonl (len); | ||
164 | aux = (char *) &block_edge[1]; | ||
165 | memcpy (aux, edges[i].label, len); | ||
166 | aux = &aux[len]; | ||
167 | } | ||
168 | (void) | ||
169 | GNUNET_DHT_put (h->dht, key, | ||
170 | DHT_REPLICATION, | ||
171 | DHT_OPT, | ||
172 | GNUNET_BLOCK_TYPE_REGEX, size, | ||
173 | (char *) block, | ||
174 | GNUNET_TIME_relative_to_absolute (DHT_TTL), | ||
175 | DHT_TTL, | ||
176 | NULL, NULL); | ||
177 | GNUNET_STATISTICS_update (h->stats, "# regex blocks stored", | ||
178 | 1, GNUNET_NO); | ||
179 | GNUNET_STATISTICS_update (h->stats, "# regex block bytes stored", | ||
180 | size, GNUNET_NO); | ||
181 | GNUNET_free (block); | ||
182 | } | ||
183 | |||
184 | |||
185 | struct REGEX_ITERNAL_Announcement * | ||
186 | REGEX_ITERNAL_announce (struct GNUNET_DHT_Handle *dht, | ||
187 | const struct GNUNET_PeerIdentity *id, | ||
188 | const char *regex, | ||
189 | uint16_t compression, | ||
190 | struct GNUNET_STATISTICS_Handle *stats) | ||
191 | { | ||
192 | struct REGEX_ITERNAL_Announcement *h; | ||
193 | |||
194 | GNUNET_assert (NULL != dht); | ||
195 | h = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Announcement)); | ||
196 | h->regex = regex; | ||
197 | h->dht = dht; | ||
198 | h->stats = stats; | ||
199 | h->id = *id; | ||
200 | h->dfa = REGEX_ITERNAL_construct_dfa (regex, | ||
201 | strlen (regex), | ||
202 | compression); | ||
203 | REGEX_ITERNAL_reannounce (h); | ||
204 | return h; | ||
205 | } | ||
206 | |||
207 | |||
208 | void | ||
209 | REGEX_ITERNAL_reannounce (struct REGEX_ITERNAL_Announcement *h) | ||
210 | { | ||
211 | GNUNET_assert (NULL != h->dfa); /* make sure to call announce first */ | ||
212 | LOG (GNUNET_ERROR_TYPE_INFO, "REGEX_ITERNAL_reannounce: %.60s\n", h->regex); | ||
213 | LOG (GNUNET_ERROR_TYPE_DEBUG, " full: %s\n", h->regex); | ||
214 | REGEX_ITERNAL_iterate_all_edges (h->dfa, ®ex_iterator, h); | ||
215 | } | ||
216 | |||
217 | |||
218 | void | ||
219 | REGEX_ITERNAL_announce_cancel (struct REGEX_ITERNAL_Announcement *h) | ||
220 | { | ||
221 | REGEX_ITERNAL_automaton_destroy (h->dfa); | ||
222 | GNUNET_free (h); | ||
223 | } | ||
224 | |||
225 | |||
226 | /******************************************************************************/ | ||
227 | |||
228 | |||
229 | /** | ||
230 | * Struct to keep state of running searches that have consumed a part of | ||
231 | * the inital string. | ||
232 | */ | ||
233 | struct RegexSearchContext | ||
234 | { | ||
235 | /** | ||
236 | * Part of the description already consumed by | ||
237 | * this particular search branch. | ||
238 | */ | ||
239 | size_t position; | ||
240 | |||
241 | /** | ||
242 | * Information about the search. | ||
243 | */ | ||
244 | struct REGEX_ITERNAL_Search *info; | ||
245 | |||
246 | /** | ||
247 | * We just want to look for one edge, the longer the better. | ||
248 | * Keep its length. | ||
249 | */ | ||
250 | unsigned int longest_match; | ||
251 | |||
252 | /** | ||
253 | * Destination hash of the longest match. | ||
254 | */ | ||
255 | struct GNUNET_HashCode hash; | ||
256 | }; | ||
257 | |||
258 | |||
259 | /** | ||
260 | * Struct to keep information of searches of services described by a regex | ||
261 | * using a user-provided string service description. | ||
262 | */ | ||
263 | struct REGEX_ITERNAL_Search | ||
264 | { | ||
265 | /** | ||
266 | * DHT handle to use, must be initialized externally. | ||
267 | */ | ||
268 | struct GNUNET_DHT_Handle *dht; | ||
269 | |||
270 | /** | ||
271 | * Optional statistics handle to report usage. Can be NULL. | ||
272 | */ | ||
273 | struct GNUNET_STATISTICS_Handle *stats; | ||
274 | |||
275 | /** | ||
276 | * User provided description of the searched service. | ||
277 | */ | ||
278 | char *description; | ||
279 | |||
280 | /** | ||
281 | * Running DHT GETs. | ||
282 | */ | ||
283 | struct GNUNET_CONTAINER_MultiHashMap *dht_get_handles; | ||
284 | |||
285 | /** | ||
286 | * Results from running DHT GETs. | ||
287 | */ | ||
288 | struct GNUNET_CONTAINER_MultiHashMap *dht_get_results; | ||
289 | |||
290 | /** | ||
291 | * Contexts, for each running DHT GET. Free all on end of search. | ||
292 | */ | ||
293 | struct RegexSearchContext **contexts; | ||
294 | |||
295 | /** | ||
296 | * Number of contexts (branches/steps in search). | ||
297 | */ | ||
298 | unsigned int n_contexts; | ||
299 | |||
300 | /** | ||
301 | * @param callback Callback for found peers. | ||
302 | */ | ||
303 | REGEX_ITERNAL_Found callback; | ||
304 | |||
305 | /** | ||
306 | * @param callback_cls Closure for @c callback. | ||
307 | */ | ||
308 | void *callback_cls; | ||
309 | }; | ||
310 | |||
311 | |||
312 | |||
313 | /** | ||
314 | * Jump to the next edge, with the longest matching token. | ||
315 | * | ||
316 | * @param block Block found in the DHT. | ||
317 | * @param size Size of the block. | ||
318 | * @param ctx Context of the search. | ||
319 | * | ||
320 | * @return GNUNET_YES if should keep iterating, GNUNET_NO otherwise. | ||
321 | */ | ||
322 | static void | ||
323 | regex_next_edge (const struct RegexBlock *block, | ||
324 | size_t size, | ||
325 | struct RegexSearchContext *ctx); | ||
326 | |||
327 | |||
328 | /** | ||
329 | * Function to process DHT string to regex matching. | ||
330 | * Called on each result obtained for the DHT search. | ||
331 | * | ||
332 | * @param cls Closure (search context). | ||
333 | * @param exp When will this value expire. | ||
334 | * @param key Key of the result. | ||
335 | * @param get_path Path of the get request. | ||
336 | * @param get_path_length Lenght of get_path. | ||
337 | * @param put_path Path of the put request. | ||
338 | * @param put_path_length Length of the put_path. | ||
339 | * @param type Type of the result. | ||
340 | * @param size Number of bytes in data. | ||
341 | * @param data Pointer to the result data. | ||
342 | */ | ||
343 | static void | ||
344 | dht_get_string_accept_handler (void *cls, struct GNUNET_TIME_Absolute exp, | ||
345 | const struct GNUNET_HashCode * key, | ||
346 | const struct GNUNET_PeerIdentity *get_path, | ||
347 | unsigned int get_path_length, | ||
348 | const struct GNUNET_PeerIdentity *put_path, | ||
349 | unsigned int put_path_length, | ||
350 | enum GNUNET_BLOCK_Type type, | ||
351 | size_t size, const void *data) | ||
352 | { | ||
353 | const struct RegexAccept *block = data; | ||
354 | struct RegexSearchContext *ctx = cls; | ||
355 | struct REGEX_ITERNAL_Search *info = ctx->info; | ||
356 | |||
357 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Got regex results from DHT!\n"); | ||
358 | LOG (GNUNET_ERROR_TYPE_INFO, " accept for %s (key %s)\n", | ||
359 | info->description, GNUNET_h2s(key)); | ||
360 | |||
361 | GNUNET_STATISTICS_update (info->stats, "# regex accepting blocks found", | ||
362 | 1, GNUNET_NO); | ||
363 | GNUNET_STATISTICS_update (info->stats, "# regex accepting block bytes found", | ||
364 | size, GNUNET_NO); | ||
365 | |||
366 | info->callback (info->callback_cls, | ||
367 | &block->id, | ||
368 | get_path, get_path_length, | ||
369 | put_path, put_path_length); | ||
370 | } | ||
371 | |||
372 | |||
373 | /** | ||
374 | * Find a path to a peer that offers a regex servcie compatible | ||
375 | * with a given string. | ||
376 | * | ||
377 | * @param key The key of the accepting state. | ||
378 | * @param ctx Context containing info about the string, tunnel, etc. | ||
379 | */ | ||
380 | static void | ||
381 | regex_find_path (const struct GNUNET_HashCode *key, | ||
382 | struct RegexSearchContext *ctx) | ||
383 | { | ||
384 | struct GNUNET_DHT_GetHandle *get_h; | ||
385 | |||
386 | LOG (GNUNET_ERROR_TYPE_DEBUG, "Found peer by service\n"); | ||
387 | LOG (GNUNET_ERROR_TYPE_INFO, " find accept for %s\n", GNUNET_h2s (key)); | ||
388 | get_h = GNUNET_DHT_get_start (ctx->info->dht, /* handle */ | ||
389 | GNUNET_BLOCK_TYPE_REGEX_ACCEPT, /* type */ | ||
390 | key, /* key to search */ | ||
391 | DHT_REPLICATION, /* replication level */ | ||
392 | DHT_OPT | GNUNET_DHT_RO_RECORD_ROUTE, | ||
393 | NULL, /* xquery */ // FIXME BLOOMFILTER | ||
394 | 0, /* xquery bits */ // FIXME BLOOMFILTER SIZE | ||
395 | &dht_get_string_accept_handler, ctx); | ||
396 | GNUNET_break (GNUNET_OK == | ||
397 | GNUNET_CONTAINER_multihashmap_put(ctx->info->dht_get_handles, | ||
398 | key, | ||
399 | get_h, | ||
400 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE)); | ||
401 | } | ||
402 | |||
403 | |||
404 | /** | ||
405 | * Function to process DHT string to regex matching. | ||
406 | * Called on each result obtained for the DHT search. | ||
407 | * | ||
408 | * @param cls closure (search context) | ||
409 | * @param exp when will this value expire | ||
410 | * @param key key of the result | ||
411 | * @param get_path path of the get request (not used) | ||
412 | * @param get_path_length lenght of get_path (not used) | ||
413 | * @param put_path path of the put request (not used) | ||
414 | * @param put_path_length length of the put_path (not used) | ||
415 | * @param type type of the result | ||
416 | * @param size number of bytes in data | ||
417 | * @param data pointer to the result data | ||
418 | * | ||
419 | * TODO: re-issue the request after certain time? cancel after X results? | ||
420 | */ | ||
421 | static void | ||
422 | dht_get_string_handler (void *cls, struct GNUNET_TIME_Absolute exp, | ||
423 | const struct GNUNET_HashCode * key, | ||
424 | const struct GNUNET_PeerIdentity *get_path, | ||
425 | unsigned int get_path_length, | ||
426 | const struct GNUNET_PeerIdentity *put_path, | ||
427 | unsigned int put_path_length, | ||
428 | enum GNUNET_BLOCK_Type type, | ||
429 | size_t size, const void *data) | ||
430 | { | ||
431 | const struct RegexBlock *block = data; | ||
432 | struct RegexSearchContext *ctx = cls; | ||
433 | struct REGEX_ITERNAL_Search *info = ctx->info; | ||
434 | void *copy; | ||
435 | size_t len; | ||
436 | char *datastore; | ||
437 | |||
438 | #if DEBUG_DHT | ||
439 | if (NULL != put_path && 0 != put_path_length) | ||
440 | { | ||
441 | datastore = GNUNET_strdup (GNUNET_i2s (&put_path[put_path_length - 1])); | ||
442 | } | ||
443 | else | ||
444 | { | ||
445 | GNUNET_asprintf (&datastore, "?? %u/%u", put_path_length, get_path_length); | ||
446 | } | ||
447 | #else | ||
448 | datastore = GNUNET_strdup ("N/A"); | ||
449 | #endif | ||
450 | |||
451 | LOG (GNUNET_ERROR_TYPE_INFO, " DHT GET result for %s (%s) at %s\n", | ||
452 | GNUNET_h2s (key), ctx->info->description, datastore); | ||
453 | GNUNET_free (datastore); | ||
454 | |||
455 | copy = GNUNET_malloc (size); | ||
456 | memcpy (copy, data, size); | ||
457 | GNUNET_break ( | ||
458 | GNUNET_OK == | ||
459 | GNUNET_CONTAINER_multihashmap_put (info->dht_get_results, | ||
460 | &((struct RegexBlock *)copy)->key, copy, | ||
461 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE) | ||
462 | ); | ||
463 | len = ntohl (block->n_proof); | ||
464 | { | ||
465 | char proof[len + 1]; | ||
466 | |||
467 | memcpy (proof, &block[1], len); | ||
468 | proof[len] = '\0'; | ||
469 | if (GNUNET_OK != REGEX_ITERNAL_check_proof (proof, key)) | ||
470 | { | ||
471 | GNUNET_break_op (0); | ||
472 | return; | ||
473 | } | ||
474 | } | ||
475 | len = strlen (info->description); | ||
476 | if (len == ctx->position) // String processed | ||
477 | { | ||
478 | if (GNUNET_YES == ntohl (block->accepting)) | ||
479 | { | ||
480 | regex_find_path (key, ctx); | ||
481 | } | ||
482 | else | ||
483 | { | ||
484 | LOG (GNUNET_ERROR_TYPE_INFO, " block not accepting!\n"); | ||
485 | // FIXME REGEX this block not successful, wait for more? start timeout? | ||
486 | } | ||
487 | return; | ||
488 | } | ||
489 | regex_next_edge (block, size, ctx); | ||
490 | } | ||
491 | |||
492 | |||
493 | /** | ||
494 | * Iterator over found existing mesh regex blocks that match an ongoing search. | ||
495 | * | ||
496 | * @param cls Closure (current context)- | ||
497 | * @param key Current key code (key for cached block). | ||
498 | * @param value Value in the hash map (cached RegexBlock). | ||
499 | * @return GNUNET_YES: we should always continue to iterate. | ||
500 | */ | ||
501 | static int | ||
502 | regex_result_iterator (void *cls, | ||
503 | const struct GNUNET_HashCode * key, | ||
504 | void *value) | ||
505 | { | ||
506 | struct RegexBlock *block = value; | ||
507 | struct RegexSearchContext *ctx = cls; | ||
508 | |||
509 | if (GNUNET_YES == ntohl(block->accepting) && | ||
510 | ctx->position == strlen (ctx->info->description)) | ||
511 | { | ||
512 | LOG (GNUNET_ERROR_TYPE_INFO, " * Found accepting known block\n"); | ||
513 | regex_find_path (key, ctx); | ||
514 | return GNUNET_YES; // We found an accept state! | ||
515 | } | ||
516 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* %u, %u, [%u]\n", | ||
517 | ctx->position, strlen(ctx->info->description), | ||
518 | ntohl(block->accepting)); | ||
519 | |||
520 | regex_next_edge (block, SIZE_MAX, ctx); | ||
521 | |||
522 | GNUNET_STATISTICS_update (ctx->info->stats, "# regex mesh blocks iterated", | ||
523 | 1, GNUNET_NO); | ||
524 | |||
525 | return GNUNET_YES; | ||
526 | } | ||
527 | |||
528 | |||
529 | /** | ||
530 | * Iterator over edges in a regex block retrieved from the DHT. | ||
531 | * | ||
532 | * @param cls Closure (context of the search). | ||
533 | * @param token Token that follows to next state. | ||
534 | * @param len Lenght of token. | ||
535 | * @param key Hash of next state. | ||
536 | * | ||
537 | * @return GNUNET_YES if should keep iterating, GNUNET_NO otherwise. | ||
538 | */ | ||
539 | static int | ||
540 | regex_edge_iterator (void *cls, | ||
541 | const char *token, | ||
542 | size_t len, | ||
543 | const struct GNUNET_HashCode *key) | ||
544 | { | ||
545 | struct RegexSearchContext *ctx = cls; | ||
546 | struct REGEX_ITERNAL_Search *info = ctx->info; | ||
547 | const char *current; | ||
548 | size_t current_len; | ||
549 | |||
550 | GNUNET_STATISTICS_update (info->stats, "# regex edges iterated", | ||
551 | 1, GNUNET_NO); | ||
552 | |||
553 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* Start of regex edge iterator\n"); | ||
554 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* descr : %s\n", info->description); | ||
555 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* posit : %u\n", ctx->position); | ||
556 | current = &info->description[ctx->position]; | ||
557 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* currt : %s\n", current); | ||
558 | current_len = strlen (info->description) - ctx->position; | ||
559 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* ctlen : %u\n", current_len); | ||
560 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* tklen : %u\n", len); | ||
561 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* token : %.*s\n", len, token); | ||
562 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* nextk : %s\n", GNUNET_h2s(key)); | ||
563 | if (len > current_len) | ||
564 | { | ||
565 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* Token too long, END\n"); | ||
566 | return GNUNET_YES; // Token too long, wont match | ||
567 | } | ||
568 | if (0 != strncmp (current, token, len)) | ||
569 | { | ||
570 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* Token doesn't match, END\n"); | ||
571 | return GNUNET_YES; // Token doesn't match | ||
572 | } | ||
573 | |||
574 | if (len > ctx->longest_match) | ||
575 | { | ||
576 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* Token is longer, KEEP\n"); | ||
577 | ctx->longest_match = len; | ||
578 | ctx->hash = *key; | ||
579 | } | ||
580 | else | ||
581 | { | ||
582 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* Token is not longer, IGNORE\n"); | ||
583 | } | ||
584 | |||
585 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* End of regex edge iterator\n"); | ||
586 | return GNUNET_YES; | ||
587 | } | ||
588 | |||
589 | |||
590 | /** | ||
591 | * Jump to the next edge, with the longest matching token. | ||
592 | * | ||
593 | * @param block Block found in the DHT. | ||
594 | * @param size Size of the block. | ||
595 | * @param ctx Context of the search. | ||
596 | * | ||
597 | * @return GNUNET_YES if should keep iterating, GNUNET_NO otherwise. | ||
598 | */ | ||
599 | static void | ||
600 | regex_next_edge (const struct RegexBlock *block, | ||
601 | size_t size, | ||
602 | struct RegexSearchContext *ctx) | ||
603 | { | ||
604 | struct RegexSearchContext *new_ctx; | ||
605 | struct REGEX_ITERNAL_Search *info = ctx->info; | ||
606 | struct GNUNET_DHT_GetHandle *get_h; | ||
607 | struct GNUNET_HashCode *hash; | ||
608 | const char *rest; | ||
609 | int result; | ||
610 | |||
611 | /* Find the longest match for the current string position, | ||
612 | * among tokens in the given block */ | ||
613 | ctx->longest_match = 0; | ||
614 | result = REGEX_ITERNAL_block_iterate (block, size, | ||
615 | ®ex_edge_iterator, ctx); | ||
616 | GNUNET_break (GNUNET_OK == result); | ||
617 | |||
618 | /* Did anything match? */ | ||
619 | if (0 == ctx->longest_match) | ||
620 | { | ||
621 | LOG (GNUNET_ERROR_TYPE_DEBUG, " no match in block\n"); | ||
622 | return; | ||
623 | } | ||
624 | |||
625 | hash = &ctx->hash; | ||
626 | new_ctx = GNUNET_malloc (sizeof (struct RegexSearchContext)); | ||
627 | new_ctx->info = info; | ||
628 | new_ctx->position = ctx->position + ctx->longest_match; | ||
629 | GNUNET_array_append (info->contexts, info->n_contexts, new_ctx); | ||
630 | |||
631 | /* Check whether we already have a DHT GET running for it */ | ||
632 | if (GNUNET_YES == | ||
633 | GNUNET_CONTAINER_multihashmap_contains (info->dht_get_handles, hash)) | ||
634 | { | ||
635 | LOG (GNUNET_ERROR_TYPE_DEBUG, "* GET for %s running, END\n", | ||
636 | GNUNET_h2s (hash)); | ||
637 | GNUNET_CONTAINER_multihashmap_get_multiple (info->dht_get_results, | ||
638 | hash, | ||
639 | ®ex_result_iterator, | ||
640 | new_ctx); | ||
641 | return; /* We are already looking for it */ | ||
642 | } | ||
643 | |||
644 | GNUNET_STATISTICS_update (info->stats, "# regex nodes traversed", | ||
645 | 1, GNUNET_NO); | ||
646 | |||
647 | /* Start search in DHT */ | ||
648 | LOG (GNUNET_ERROR_TYPE_INFO, " looking for %s\n", GNUNET_h2s (hash)); | ||
649 | rest = &new_ctx->info->description[new_ctx->position]; | ||
650 | get_h = | ||
651 | GNUNET_DHT_get_start (info->dht, /* handle */ | ||
652 | GNUNET_BLOCK_TYPE_REGEX, /* type */ | ||
653 | hash, /* key to search */ | ||
654 | DHT_REPLICATION, /* replication level */ | ||
655 | DHT_OPT, | ||
656 | rest, /* xquery */ | ||
657 | // FIXME add BLOOMFILTER to exclude filtered peers | ||
658 | strlen(rest) + 1, /* xquery bits */ | ||
659 | // FIXME add BLOOMFILTER SIZE | ||
660 | &dht_get_string_handler, new_ctx); | ||
661 | if (GNUNET_OK != | ||
662 | GNUNET_CONTAINER_multihashmap_put(info->dht_get_handles, | ||
663 | hash, | ||
664 | get_h, | ||
665 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST)) | ||
666 | { | ||
667 | GNUNET_break (0); | ||
668 | return; | ||
669 | } | ||
670 | } | ||
671 | |||
672 | |||
673 | struct REGEX_ITERNAL_Search * | ||
674 | REGEX_ITERNAL_search (struct GNUNET_DHT_Handle *dht, | ||
675 | const char *string, | ||
676 | REGEX_ITERNAL_Found callback, | ||
677 | void *callback_cls, | ||
678 | struct GNUNET_STATISTICS_Handle *stats) | ||
679 | { | ||
680 | struct REGEX_ITERNAL_Search *h; | ||
681 | struct GNUNET_DHT_GetHandle *get_h; | ||
682 | struct RegexSearchContext *ctx; | ||
683 | struct GNUNET_HashCode key; | ||
684 | size_t size; | ||
685 | size_t len; | ||
686 | |||
687 | /* Initialize handle */ | ||
688 | LOG (GNUNET_ERROR_TYPE_INFO, "REGEX_ITERNAL_search: %s\n", string); | ||
689 | GNUNET_assert (NULL != dht); | ||
690 | GNUNET_assert (NULL != callback); | ||
691 | h = GNUNET_malloc (sizeof (struct REGEX_ITERNAL_Search)); | ||
692 | h->dht = dht; | ||
693 | h->description = GNUNET_strdup (string); | ||
694 | h->callback = callback; | ||
695 | h->callback_cls = callback_cls; | ||
696 | h->stats = stats; | ||
697 | h->dht_get_handles = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_NO); | ||
698 | h->dht_get_results = GNUNET_CONTAINER_multihashmap_create (32, GNUNET_YES); | ||
699 | |||
700 | /* Initialize context */ | ||
701 | len = strlen (string); | ||
702 | size = REGEX_ITERNAL_get_first_key (string, len, &key); | ||
703 | ctx = GNUNET_malloc (sizeof (struct RegexSearchContext)); | ||
704 | ctx->position = size; | ||
705 | ctx->info = h; | ||
706 | GNUNET_array_append (h->contexts, h->n_contexts, ctx); | ||
707 | LOG (GNUNET_ERROR_TYPE_DEBUG, " consumed %u bits out of %u\n", size, len); | ||
708 | LOG (GNUNET_ERROR_TYPE_INFO, " looking for %s\n", GNUNET_h2s (&key)); | ||
709 | |||
710 | /* Start search in DHT */ | ||
711 | get_h = GNUNET_DHT_get_start (h->dht, /* handle */ | ||
712 | GNUNET_BLOCK_TYPE_REGEX, /* type */ | ||
713 | &key, /* key to search */ | ||
714 | DHT_REPLICATION, /* replication level */ | ||
715 | DHT_OPT, | ||
716 | &h->description[size], /* xquery */ | ||
717 | // FIXME add BLOOMFILTER to exclude filtered peers | ||
718 | len + 1 - size, /* xquery bits */ | ||
719 | // FIXME add BLOOMFILTER SIZE | ||
720 | &dht_get_string_handler, ctx); | ||
721 | GNUNET_break ( | ||
722 | GNUNET_OK == | ||
723 | GNUNET_CONTAINER_multihashmap_put (h->dht_get_handles, | ||
724 | &key, | ||
725 | get_h, | ||
726 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST) | ||
727 | ); | ||
728 | |||
729 | return h; | ||
730 | } | ||
731 | |||
732 | |||
733 | /** | ||
734 | * Iterator over hash map entries to cancel DHT GET requests after a | ||
735 | * successful connect_by_string. | ||
736 | * | ||
737 | * @param cls Closure (unused). | ||
738 | * @param key Current key code (unused). | ||
739 | * @param value Value in the hash map (get handle). | ||
740 | * @return GNUNET_YES if we should continue to iterate, | ||
741 | * GNUNET_NO if not. | ||
742 | */ | ||
743 | static int | ||
744 | regex_cancel_dht_get (void *cls, | ||
745 | const struct GNUNET_HashCode * key, | ||
746 | void *value) | ||
747 | { | ||
748 | struct GNUNET_DHT_GetHandle *h = value; | ||
749 | |||
750 | GNUNET_DHT_get_stop (h); | ||
751 | return GNUNET_YES; | ||
752 | } | ||
753 | |||
754 | |||
755 | /** | ||
756 | * Iterator over hash map entries to free MeshRegexBlocks stored during the | ||
757 | * search for connect_by_string. | ||
758 | * | ||
759 | * @param cls Closure (unused). | ||
760 | * @param key Current key code (unused). | ||
761 | * @param value MeshRegexBlock in the hash map. | ||
762 | * @return GNUNET_YES if we should continue to iterate, | ||
763 | * GNUNET_NO if not. | ||
764 | */ | ||
765 | static int | ||
766 | regex_free_result (void *cls, | ||
767 | const struct GNUNET_HashCode * key, | ||
768 | void *value) | ||
769 | { | ||
770 | |||
771 | GNUNET_free (value); | ||
772 | return GNUNET_YES; | ||
773 | } | ||
774 | |||
775 | |||
776 | /** | ||
777 | * Cancel an ongoing regex search in the DHT and free all resources. | ||
778 | * | ||
779 | * @param ctx The search context. | ||
780 | */ | ||
781 | static void | ||
782 | regex_cancel_search (struct REGEX_ITERNAL_Search *ctx) | ||
783 | { | ||
784 | GNUNET_free (ctx->description); | ||
785 | GNUNET_CONTAINER_multihashmap_iterate (ctx->dht_get_handles, | ||
786 | ®ex_cancel_dht_get, NULL); | ||
787 | GNUNET_CONTAINER_multihashmap_iterate (ctx->dht_get_results, | ||
788 | ®ex_free_result, NULL); | ||
789 | GNUNET_CONTAINER_multihashmap_destroy (ctx->dht_get_results); | ||
790 | GNUNET_CONTAINER_multihashmap_destroy (ctx->dht_get_handles); | ||
791 | if (0 < ctx->n_contexts) | ||
792 | { | ||
793 | int i; | ||
794 | |||
795 | for (i = 0; i < ctx->n_contexts; i++) | ||
796 | { | ||
797 | GNUNET_free (ctx->contexts[i]); | ||
798 | } | ||
799 | GNUNET_free (ctx->contexts); | ||
800 | } | ||
801 | } | ||
802 | |||
803 | void | ||
804 | REGEX_ITERNAL_search_cancel (struct REGEX_ITERNAL_Search *h) | ||
805 | { | ||
806 | regex_cancel_search (h); | ||
807 | GNUNET_free (h); | ||
808 | } | ||
809 | |||
810 | |||
811 | |||
812 | /* end of regex_dht.c */ | ||