2 This file is part of GNUnet.
3 (C) 2012,2013 Christian Grothoff (and other contributing authors)
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.
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.
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.
21 * @author Bartlomiej Polot
22 * @file regex/regex_block_lib.c
23 * @brief functions for manipulating non-accept blocks stored for
27 #include "regex_block_lib.h"
29 #define LOG(kind,...) GNUNET_log_from (kind,"regex-bck",__VA_ARGS__)
31 GNUNET_NETWORK_STRUCT_BEGIN
34 * @brief Block to announce a regex state.
40 * Length of the proof regex string.
42 uint16_t proof_len GNUNET_PACKED;
45 * Is this state an accepting state?
47 int16_t is_accepting GNUNET_PACKED;
50 * Numer of edges parting from this state.
52 uint32_t n_edges GNUNET_PACKED;
54 /* char proof[n_proof] */
55 /* struct RegexEdge edges[n_edges] */
60 * @brief A RegexBlock contains one or more of this struct in the payload.
65 * Destination of this edge.
67 struct GNUNET_HashCode key;
70 * Length of the token towards the new state.
72 uint32_t n_token GNUNET_PACKED;
74 /* char token[n_token] */
78 GNUNET_NETWORK_STRUCT_END
82 * Test if this block is marked as being an accept state.
84 * @param block block to test
85 * @return GNUNET_YES if the block is accepting, GNUNET_NO if not
88 GNUNET_BLOCK_is_accepting (const struct RegexBlock *block)
90 return ntohs (block->is_accepting);
95 * Check if the given 'proof' matches the given 'key'.
97 * @param proof partial regex of a state
98 * @param proof_len number of bytes in 'proof'
99 * @param key hash of a state.
101 * @return GNUNET_OK if the proof is valid for the given key.
104 REGEX_BLOCK_check_proof (const char *proof,
106 const struct GNUNET_HashCode *key)
108 struct GNUNET_HashCode key_check;
110 if ( (NULL == proof) || (NULL == key))
112 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
115 GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
117 GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
122 * Struct to keep track of the xquery while iterating all the edges in a block.
124 struct CheckEdgeContext
127 * Xquery: string we are looking for.
132 * Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
140 * Iterator over all edges in a block, checking for a presence of a given query.
142 * @param cls Closure, (xquery context).
143 * @param token Token that follows to next state.
144 * @param len Lenght of token.
145 * @param key Hash of next state.
147 * @return GNUNET_YES, to keep iterating
150 check_edge (void *cls,
153 const struct GNUNET_HashCode *key)
155 struct CheckEdgeContext *ctx = cls;
157 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
158 "edge %.*s [%u]: %s->%s\n",
159 (int) len, token, len, GNUNET_h2s(key));
160 if (NULL == ctx->xquery)
162 if (strlen (ctx->xquery) < len)
163 return GNUNET_YES; /* too long */
164 if (0 == strncmp (ctx->xquery, token, len))
165 ctx->found = GNUNET_OK;
166 return GNUNET_YES; /* keep checking for malformed data! */
171 * Check if the regex block is well formed, including all edges.
173 * @param block The start of the block.
174 * @param size The size of the block.
175 * @param query the query for the block
176 * @param xquery String describing the edge we are looking for.
177 * Can be NULL in case this is a put block.
179 * @return GNUNET_OK in case it's fine.
180 * GNUNET_NO in case the xquery exists and is not found (IRRELEVANT).
181 * GNUNET_SYSERR if the block is invalid.
184 REGEX_BLOCK_check (const struct RegexBlock *block,
186 const struct GNUNET_HashCode *query,
189 struct CheckEdgeContext ctx;
193 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
194 "Checking block with xquery `%s'\n",
195 NULL != xquery ? xquery : "NULL");
196 len = ntohs (block->proof_len);
197 if (size < sizeof (struct RegexBlock) + len)
200 return GNUNET_SYSERR;
202 if (GNUNET_OK != REGEX_BLOCK_check_proof ((const char *) &block[1], len, query))
205 return GNUNET_SYSERR;
207 if ( (GNUNET_YES == ntohs (block->is_accepting)) &&
208 ( (NULL == xquery) || ('\0' == xquery[0]) ) )
211 ctx.found = GNUNET_NO;
212 res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
213 if (GNUNET_SYSERR == res)
214 return GNUNET_SYSERR;
222 * Obtain the key that a particular block is to be stored under.
224 * @param block block to get the key from
225 * @param block_len number of bytes in block
226 * @param query where to store the key
227 * @return GNUNET_OK on success, GNUNET_SYSERR if the block is malformed
230 REGEX_BLOCK_get_key (const struct RegexBlock *block,
232 struct GNUNET_HashCode *key)
236 len = ntohs (block->proof_len);
237 if (block_len < sizeof (struct RegexBlock) + len)
240 return GNUNET_SYSERR;
242 GNUNET_CRYPTO_hash (&block[1], len, key);
248 * Iterate over all edges of a block of a regex state.
250 * @param block Block to iterate over.
251 * @param size Size of block.
252 * @param iterator Function to call on each edge in the block.
253 * @param iter_cls Closure for the iterator.
255 * @return GNUNET_SYSERR if an error has been encountered.
256 * GNUNET_OK if no error has been encountered.
257 * Note that if the iterator stops the iteration by returning
258 * GNUNET_NO, the block will no longer be checked for further errors.
259 * The return value will be GNUNET_OK meaning that no errors were
260 * found until the edge last notified to the iterator, but there might
261 * be errors in further edges.
264 REGEX_BLOCK_iterate (const struct RegexBlock *block,
266 REGEX_INTERNAL_EgdeIterator iterator,
269 struct RegexEdge *edge;
271 unsigned int n_token;
276 offset = sizeof (struct RegexBlock);
277 if (offset >= size) /* Is it safe to access the regex block? */
280 return GNUNET_SYSERR;
282 n = ntohs (block->proof_len);
284 if (offset >= size) /* Is it safe to access the regex proof? */
287 return GNUNET_SYSERR;
289 aux = (char *) &block[1]; /* Skip regex block */
290 aux = &aux[n]; /* Skip regex proof */
291 n = ntohl (block->n_edges);
292 LOG (GNUNET_ERROR_TYPE_DEBUG,
293 "Start iterating block of size %u, proof %u, off %u edges %u\n",
294 size, ntohs (block->proof_len), offset, n);
295 /* aux always points at the end of the previous block */
296 for (i = 0; i < n; i++)
298 offset += sizeof (struct RegexEdge);
299 LOG (GNUNET_ERROR_TYPE_DEBUG, "* Edge %u, off %u\n", i, offset);
300 if (offset >= size) /* Is it safe to access the next edge block? */
302 LOG (GNUNET_ERROR_TYPE_WARNING,
303 "* Size not enough for RegexEdge, END\n");
305 return GNUNET_SYSERR;
307 edge = (struct RegexEdge *) aux;
308 n_token = ntohl (edge->n_token);
310 LOG (GNUNET_ERROR_TYPE_DEBUG,
311 "* Token length %u, off %u\n", n_token, offset);
312 if (offset > size) /* Is it safe to access the edge token? */
314 LOG (GNUNET_ERROR_TYPE_WARNING,
315 "* Size not enough for edge token, END\n");
317 return GNUNET_SYSERR;
319 aux = (char *) &edge[1]; /* Skip edge block */
320 if (NULL != iterator)
321 if (GNUNET_NO == iterator (iter_cls, aux, n_token, &edge->key))
323 aux = &aux[n_token]; /* Skip edge token */
325 /* The total size should be exactly the size of (regex + all edges) blocks
326 * If size == -1, block is from cache and therefore previously checked and
327 * assumed correct. */
328 if ( (offset != size) && (SIZE_MAX != size) )
331 return GNUNET_SYSERR;
338 * Construct a regex block to be stored in the DHT.
340 * @param proof proof string for the block
341 * @param num_edges number of edges in the block
342 * @param edges the edges of the block
343 * @param accepting is this an accepting state
344 * @param rsize set to the size of the returned block (OUT-only)
345 * @return the regex block, NULL on error
348 REGEX_BLOCK_create (const char *proof,
349 unsigned int num_edges,
350 const struct REGEX_BLOCK_Edge *edges,
354 struct RegexBlock *block;
355 struct RegexEdge *block_edge;
362 len = strlen (proof);
363 if (len > UINT16_MAX)
368 size = sizeof (struct RegexBlock) + len;
369 block = GNUNET_malloc (size);
370 block->proof_len = htons (len);
371 block->n_edges = htonl (num_edges);
372 block->is_accepting = htons (accepting);
374 /* Store the proof at the end of the block. */
375 aux = (char *) &block[1];
376 memcpy (aux, proof, len);
379 /* Store each edge in a variable length MeshEdge struct at the
380 * very end of the MeshRegexBlock structure.
382 for (i = 0; i < num_edges; i++)
384 /* aux points at the end of the last block */
385 len = strlen (edges[i].label);
386 size += sizeof (struct RegexEdge) + len;
387 // Calculate offset FIXME is this ok? use size instead?
388 offset = aux - (char *) block;
389 block = GNUNET_realloc (block, size);
390 aux = &((char *) block)[offset];
391 block_edge = (struct RegexEdge *) aux;
392 block_edge->key = edges[i].destination;
393 block_edge->n_token = htonl (len);
394 aux = (char *) &block_edge[1];
395 memcpy (aux, edges[i].label, len);
403 /* end of regex_block_lib.c */