aboutsummaryrefslogtreecommitdiff
path: root/src/regex/regex_block_lib.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/regex/regex_block_lib.c')
-rw-r--r--src/regex/regex_block_lib.c474
1 files changed, 0 insertions, 474 deletions
diff --git a/src/regex/regex_block_lib.c b/src/regex/regex_block_lib.c
deleted file mode 100644
index cbfb553ce..000000000
--- a/src/regex/regex_block_lib.c
+++ /dev/null
@@ -1,474 +0,0 @@
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2012,2013 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your 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 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20/**
21 * @author Bartlomiej Polot
22 * @file regex/regex_block_lib.c
23 * @brief functions for manipulating non-accept blocks stored for
24 * regex in the DHT
25 */
26#include "platform.h"
27#include "regex_block_lib.h"
28#include "gnunet_constants.h"
29
30#define LOG(kind, ...) GNUNET_log_from (kind, "regex-bck", __VA_ARGS__)
31
32GNUNET_NETWORK_STRUCT_BEGIN
33
34/**
35 * Information for each edge.
36 */
37struct EdgeInfo
38{
39 /**
40 * Index of the destination of this edge in the
41 * unique destinations array.
42 */
43 uint16_t destination_index GNUNET_PACKED;
44
45 /**
46 * Number of bytes the token for this edge takes in the
47 * token area.
48 */
49 uint16_t token_length GNUNET_PACKED;
50};
51
52
53/**
54 * @brief Block to announce a regex state.
55 */
56struct RegexBlock
57{
58 /**
59 * Length of the proof regex string.
60 */
61 uint16_t proof_len GNUNET_PACKED;
62
63 /**
64 * Is this state an accepting state?
65 */
66 int16_t is_accepting GNUNET_PACKED;
67
68 /**
69 * Number of edges parting from this state.
70 */
71 uint16_t num_edges GNUNET_PACKED;
72
73 /**
74 * Number of unique destinations reachable from this state.
75 */
76 uint16_t num_destinations GNUNET_PACKED;
77
78 /* followed by 'struct GNUNET_HashCode[num_destinations]' */
79
80 /* followed by 'struct EdgeInfo[edge_destination_indices]' */
81
82 /* followed by 'char proof[n_proof]', NOT 0-terminated */
83
84 /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
85 essentially all of the tokens one after the other in the
86 order of the edges; tokens are NOT 0-terminated */
87};
88
89
90GNUNET_NETWORK_STRUCT_END
91
92
93/**
94 * Test if this block is marked as being an accept state.
95 *
96 * @param block block to test
97 * @param size number of bytes in block
98 * @return #GNUNET_YES if the block is accepting, #GNUNET_NO if not
99 */
100int
101GNUNET_BLOCK_is_accepting (const struct RegexBlock *block,
102 size_t size)
103{
104 if (size < sizeof(struct RegexBlock))
105 {
106 GNUNET_break_op (0);
107 return GNUNET_SYSERR;
108 }
109 return ntohs (block->is_accepting);
110}
111
112
113/**
114 * Check if the given 'proof' matches the given 'key'.
115 *
116 * @param proof partial regex of a state
117 * @param proof_len number of bytes in 'proof'
118 * @param key hash of a state.
119 * @return #GNUNET_OK if the proof is valid for the given key.
120 */
121int
122REGEX_BLOCK_check_proof (const char *proof,
123 size_t proof_len,
124 const struct GNUNET_HashCode *key)
125{
126 struct GNUNET_HashCode key_check;
127
128 if ((NULL == proof) || (NULL == key))
129 {
130 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
131 return GNUNET_NO;
132 }
133 GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
134 return (0 ==
135 GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
136}
137
138
139/**
140 * Struct to keep track of the xquery while iterating all the edges in a block.
141 */
142struct CheckEdgeContext
143{
144 /**
145 * Xquery: string we are looking for.
146 */
147 const char *xquery;
148
149 /**
150 * Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
151 */
152 int found;
153};
154
155
156/**
157 * Iterator over all edges in a block, checking for a presence of a given query.
158 *
159 * @param cls Closure, (xquery context).
160 * @param token Token that follows to next state.
161 * @param len Length of token.
162 * @param key Hash of next state.
163 *
164 * @return #GNUNET_YES, to keep iterating
165 */
166static int
167check_edge (void *cls,
168 const char *token,
169 size_t len,
170 const struct GNUNET_HashCode *key)
171{
172 struct CheckEdgeContext *ctx = cls;
173
174 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
175 "edge %.*s [%u]: %s\n",
176 (int) len,
177 token,
178 (unsigned int) len,
179 GNUNET_h2s (key));
180 if (NULL == ctx->xquery)
181 return GNUNET_YES;
182 if (strlen (ctx->xquery) < len)
183 return GNUNET_YES; /* too long */
184 if (0 == strncmp (ctx->xquery, token, len))
185 ctx->found = GNUNET_OK;
186 return GNUNET_YES; /* keep checking for malformed data! */
187}
188
189
190/**
191 * Check if the regex block is well formed, including all edges.
192 *
193 * @param block The start of the block.
194 * @param size The size of the block.
195 * @param query the query for the block
196 * @param xquery String describing the edge we are looking for.
197 * Can be NULL in case this is a put block.
198 * @return #GNUNET_OK in case it's fine.
199 * #GNUNET_NO in case the xquery exists and is not found (IRRELEVANT).
200 * #GNUNET_SYSERR if the block is invalid.
201 */
202int
203REGEX_BLOCK_check (const struct RegexBlock *block,
204 size_t size,
205 const struct GNUNET_HashCode *query,
206 const char *xquery)
207{
208 struct GNUNET_HashCode key;
209 struct CheckEdgeContext ctx;
210 int res;
211
212 LOG (GNUNET_ERROR_TYPE_DEBUG,
213 "Block check\n");
214 if (GNUNET_OK !=
215 REGEX_BLOCK_get_key (block, size,
216 &key))
217 {
218 GNUNET_break_op (0);
219 return GNUNET_SYSERR;
220 }
221 if ((NULL != query) &&
222 (0 != GNUNET_memcmp (&key,
223 query)) )
224 {
225 GNUNET_break_op (0);
226 return GNUNET_SYSERR;
227 }
228 if ((GNUNET_YES == ntohs (block->is_accepting)) &&
229 ((NULL == xquery) || ('\0' == xquery[0])))
230 {
231 LOG (GNUNET_ERROR_TYPE_DEBUG,
232 " out! Is accepting: %u, xquery %p\n",
233 ntohs (block->is_accepting),
234 xquery);
235 return GNUNET_OK;
236 }
237 ctx.xquery = xquery;
238 ctx.found = GNUNET_NO;
239 res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
240 if (GNUNET_SYSERR == res)
241 return GNUNET_SYSERR;
242 if (NULL == xquery)
243 return GNUNET_YES;
244 LOG (GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
245 return ctx.found;
246}
247
248
249/**
250 * Obtain the key that a particular block is to be stored under.
251 *
252 * @param block block to get the key from
253 * @param block_len number of bytes in block
254 * @param key where to store the key
255 * @return #GNUNET_OK on success, #GNUNET_SYSERR if the block is malformed
256 */
257int
258REGEX_BLOCK_get_key (const struct RegexBlock *block,
259 size_t block_len,
260 struct GNUNET_HashCode *key)
261{
262 uint16_t len;
263 const struct GNUNET_HashCode *destinations;
264 const struct EdgeInfo *edges;
265 uint16_t num_destinations;
266 uint16_t num_edges;
267 size_t total;
268
269 if (block_len < sizeof(struct RegexBlock))
270 {
271 GNUNET_break_op (0);
272 return GNUNET_SYSERR;
273 }
274 num_destinations = ntohs (block->num_destinations);
275 num_edges = ntohs (block->num_edges);
276 len = ntohs (block->proof_len);
277 destinations = (const struct GNUNET_HashCode *) &block[1];
278 edges = (const struct EdgeInfo *) &destinations[num_destinations];
279 total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
280 GNUNET_HashCode)
281 + num_edges * sizeof(struct EdgeInfo) + len;
282 if (block_len < total)
283 {
284 GNUNET_break_op (0);
285 return GNUNET_SYSERR;
286 }
287 GNUNET_CRYPTO_hash (&edges[num_edges], len, key);
288 return GNUNET_OK;
289}
290
291
292/**
293 * Iterate over all edges of a block of a regex state.
294 *
295 * @param block Block to iterate over.
296 * @param size Size of @a block.
297 * @param iterator Function to call on each edge in the block.
298 * @param iter_cls Closure for the @a iterator.
299 * @return #GNUNET_SYSERR if an error has been encountered.
300 * #GNUNET_OK if no error has been encountered.
301 * Note that if the iterator stops the iteration by returning
302 * #GNUNET_NO, the block will no longer be checked for further errors.
303 * The return value will be GNUNET_OK meaning that no errors were
304 * found until the edge last notified to the iterator, but there might
305 * be errors in further edges.
306 */
307int
308REGEX_BLOCK_iterate (const struct RegexBlock *block,
309 size_t size,
310 REGEX_INTERNAL_EgdeIterator iterator,
311 void *iter_cls)
312{
313 uint16_t len;
314 const struct GNUNET_HashCode *destinations;
315 const struct EdgeInfo *edges;
316 const char *aux;
317 uint16_t num_destinations;
318 uint16_t num_edges;
319 size_t total;
320 unsigned int n;
321 size_t off;
322
323 LOG (GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
324 if (size < sizeof(struct RegexBlock))
325 {
326 GNUNET_break_op (0);
327 return GNUNET_SYSERR;
328 }
329 num_destinations = ntohs (block->num_destinations);
330 num_edges = ntohs (block->num_edges);
331 len = ntohs (block->proof_len);
332 destinations = (const struct GNUNET_HashCode *) &block[1];
333 edges = (const struct EdgeInfo *) &destinations[num_destinations];
334 aux = (const char *) &edges[num_edges];
335 total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
336 GNUNET_HashCode)
337 + num_edges * sizeof(struct EdgeInfo) + len;
338 if (size < total)
339 {
340 GNUNET_break_op (0);
341 return GNUNET_SYSERR;
342 }
343 for (n = 0; n < num_edges; n++)
344 total += ntohs (edges[n].token_length);
345 if (size != total)
346 {
347 fprintf (stderr, "Expected %u, got %u\n",
348 (unsigned int) size,
349 (unsigned int) total);
350 GNUNET_break_op (0);
351 return GNUNET_SYSERR;
352 }
353 off = len;
354 LOG (GNUNET_ERROR_TYPE_DEBUG,
355 "Start iterating block of size %lu, proof %u, off %lu edges %u\n",
356 (unsigned long) size, len, (unsigned long) off, n);
357 /* &aux[off] always points to our token */
358 for (n = 0; n < num_edges; n++)
359 {
360 LOG (GNUNET_ERROR_TYPE_DEBUG,
361 "Edge %u/%u, off %lu tokenlen %u (%.*s)\n",
362 n + 1, num_edges, (unsigned long) off,
363 ntohs (edges[n].token_length), ntohs (edges[n].token_length),
364 &aux[off]);
365 if (NULL != iterator)
366 if (GNUNET_NO == iterator (iter_cls,
367 &aux[off],
368 ntohs (edges[n].token_length),
369 &destinations[ntohs (
370 edges[n].destination_index)]))
371 return GNUNET_OK;
372 off += ntohs (edges[n].token_length);
373 }
374 return GNUNET_OK;
375}
376
377
378/**
379 * Construct a regex block to be stored in the DHT.
380 *
381 * @param proof proof string for the block
382 * @param num_edges number of edges in the block
383 * @param edges the edges of the block
384 * @param accepting is this an accepting state
385 * @param rsize set to the size of the returned block (OUT-only)
386 * @return the regex block, NULL on error
387 */
388struct RegexBlock *
389REGEX_BLOCK_create (const char *proof,
390 unsigned int num_edges,
391 const struct REGEX_BLOCK_Edge *edges,
392 int accepting,
393 size_t *rsize)
394{
395 struct RegexBlock *block;
396 struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
397 uint16_t destination_indices[num_edges];
398 struct GNUNET_HashCode *dests;
399 struct EdgeInfo *edgeinfos;
400 size_t off;
401 size_t len;
402 size_t total;
403 size_t slen;
404 unsigned int unique_destinations;
405 unsigned int j;
406 unsigned int i;
407 char *aux;
408
409 len = strlen (proof);
410 if (len > UINT16_MAX)
411 {
412 GNUNET_break (0);
413 return NULL;
414 }
415 unique_destinations = 0;
416 total = sizeof(struct RegexBlock) + len;
417 for (i = 0; i < num_edges; i++)
418 {
419 slen = strlen (edges[i].label);
420 if (slen > UINT16_MAX)
421 {
422 GNUNET_break (0);
423 return NULL;
424 }
425 total += slen;
426 for (j = 0; j < unique_destinations; j++)
427 if (0 == memcmp (&destinations[j],
428 &edges[i].destination,
429 sizeof(struct GNUNET_HashCode)))
430 break;
431 if (j >= 1024)
432 {
433 GNUNET_break (0);
434 return NULL;
435 }
436 destination_indices[i] = j;
437 if (j == unique_destinations)
438 destinations[unique_destinations++] = edges[i].destination;
439 }
440 total += num_edges * sizeof(struct EdgeInfo) + unique_destinations
441 * sizeof(struct GNUNET_HashCode);
442 if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
443 {
444 GNUNET_break (0);
445 return NULL;
446 }
447 block = GNUNET_malloc (total);
448 block->proof_len = htons (len);
449 block->is_accepting = htons (accepting);
450 block->num_edges = htons (num_edges);
451 block->num_destinations = htons (unique_destinations);
452 dests = (struct GNUNET_HashCode *) &block[1];
453 GNUNET_memcpy (dests, destinations, sizeof(struct GNUNET_HashCode)
454 * unique_destinations);
455 edgeinfos = (struct EdgeInfo *) &dests[unique_destinations];
456 aux = (char *) &edgeinfos[num_edges];
457 off = len;
458 GNUNET_memcpy (aux, proof, len);
459 for (i = 0; i < num_edges; i++)
460 {
461 slen = strlen (edges[i].label);
462 edgeinfos[i].token_length = htons ((uint16_t) slen);
463 edgeinfos[i].destination_index = htons (destination_indices[i]);
464 GNUNET_memcpy (&aux[off],
465 edges[i].label,
466 slen);
467 off += slen;
468 }
469 *rsize = total;
470 return block;
471}
472
473
474/* end of regex_block_lib.c */