GNUnet  0.10.x
regex_block_lib.c
Go to the documentation of this file.
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 */
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 
33 
37 struct EdgeInfo
38 {
44 
50 };
51 
52 
56 struct RegexBlock
57 {
58 
62  uint16_t proof_len GNUNET_PACKED;
63 
67  int16_t is_accepting GNUNET_PACKED;
68 
72  uint16_t num_edges GNUNET_PACKED;
73 
77  uint16_t num_destinations GNUNET_PACKED;
78 
79  /* followed by 'struct GNUNET_HashCode[num_destinations]' */
80 
81  /* followed by 'struct EdgeInfo[edge_destination_indices]' */
82 
83  /* followed by 'char proof[n_proof]', NOT 0-terminated */
84 
85  /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
86  essentially all of the tokens one after the other in the
87  order of the edges; tokens are NOT 0-terminated */
88 
89 };
90 
91 
93 
94 
102 int
104  size_t size)
105 {
106  if (size < sizeof (struct RegexBlock))
107  {
108  GNUNET_break_op (0);
109  return GNUNET_SYSERR;
110  }
111  return ntohs (block->is_accepting);
112 }
113 
114 
123 int
125  size_t proof_len,
126  const struct GNUNET_HashCode *key)
127 {
128  struct GNUNET_HashCode key_check;
129 
130  if ( (NULL == proof) || (NULL == key))
131  {
132  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
133  return GNUNET_NO;
134  }
135  GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
136  return (0 ==
137  GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
138 }
139 
140 
145 {
149  const char *xquery;
150 
154  int found;
155 
156 };
157 
158 
169 static int
170 check_edge (void *cls,
171  const char *token,
172  size_t len,
173  const struct GNUNET_HashCode *key)
174 {
175  struct CheckEdgeContext *ctx = cls;
176 
178  "edge %.*s [%u]: %s\n",
179  (int) len,
180  token,
181  (unsigned int) len,
182  GNUNET_h2s (key));
183  if (NULL == ctx->xquery)
184  return GNUNET_YES;
185  if (strlen (ctx->xquery) < len)
186  return GNUNET_YES; /* too long */
187  if (0 == strncmp (ctx->xquery, token, len))
188  ctx->found = GNUNET_OK;
189  return GNUNET_YES; /* keep checking for malformed data! */
190 }
191 
192 
205 int
206 REGEX_BLOCK_check (const struct RegexBlock *block,
207  size_t size,
208  const struct GNUNET_HashCode *query,
209  const char *xquery)
210 {
211  struct GNUNET_HashCode key;
212  struct CheckEdgeContext ctx;
213  int res;
214 
216  "Block check\n");
217  if (GNUNET_OK !=
218  REGEX_BLOCK_get_key (block, size,
219  &key))
220  {
221  GNUNET_break_op (0);
222  return GNUNET_SYSERR;
223  }
224  if (NULL != query &&
225  0 != GNUNET_memcmp (&key,
226  query))
227  {
228  GNUNET_break_op (0);
229  return GNUNET_SYSERR;
230  }
231  if ( (GNUNET_YES == ntohs (block->is_accepting)) &&
232  ( (NULL == xquery) || ('\0' == xquery[0]) ) )
233  {
235  " out! Is accepting: %u, xquery %p\n",
236  ntohs(block->is_accepting),
237  xquery);
238  return GNUNET_OK;
239  }
240  ctx.xquery = xquery;
241  ctx.found = GNUNET_NO;
242  res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
243  if (GNUNET_SYSERR == res)
244  return GNUNET_SYSERR;
245  if (NULL == xquery)
246  return GNUNET_YES;
247  LOG (GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
248  return ctx.found;
249 }
250 
251 
260 int
261 REGEX_BLOCK_get_key (const struct RegexBlock *block,
262  size_t block_len,
263  struct GNUNET_HashCode *key)
264 {
265  uint16_t len;
266  const struct GNUNET_HashCode *destinations;
267  const struct EdgeInfo *edges;
268  uint16_t num_destinations;
269  uint16_t num_edges;
270  size_t total;
271 
272  if (block_len < sizeof (struct RegexBlock))
273  {
274  GNUNET_break_op (0);
275  return GNUNET_SYSERR;
276  }
277  num_destinations = ntohs (block->num_destinations);
278  num_edges = ntohs (block->num_edges);
279  len = ntohs (block->proof_len);
280  destinations = (const struct GNUNET_HashCode *) &block[1];
281  edges = (const struct EdgeInfo *) &destinations[num_destinations];
282  total = sizeof (struct RegexBlock) + num_destinations * sizeof (struct GNUNET_HashCode) + num_edges * sizeof (struct EdgeInfo) + len;
283  if (block_len < total)
284  {
285  GNUNET_break_op (0);
286  return GNUNET_SYSERR;
287  }
288  GNUNET_CRYPTO_hash (&edges[num_edges], len, key);
289  return GNUNET_OK;
290 }
291 
292 
308 int
309 REGEX_BLOCK_iterate (const struct RegexBlock *block,
310  size_t size,
312  void *iter_cls)
313 {
314  uint16_t len;
315  const struct GNUNET_HashCode *destinations;
316  const struct EdgeInfo *edges;
317  const char *aux;
318  uint16_t num_destinations;
319  uint16_t num_edges;
320  size_t total;
321  unsigned int n;
322  size_t off;
323 
324  LOG (GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
325  if (size < sizeof (struct RegexBlock))
326  {
327  GNUNET_break_op (0);
328  return GNUNET_SYSERR;
329  }
330  num_destinations = ntohs (block->num_destinations);
331  num_edges = ntohs (block->num_edges);
332  len = ntohs (block->proof_len);
333  destinations = (const struct GNUNET_HashCode *) &block[1];
334  edges = (const struct EdgeInfo *) &destinations[num_destinations];
335  aux = (const char *) &edges[num_edges];
336  total = sizeof (struct RegexBlock) + num_destinations * sizeof (struct GNUNET_HashCode) + num_edges * sizeof (struct EdgeInfo) + len;
337  if (size < total)
338  {
339  GNUNET_break_op (0);
340  return GNUNET_SYSERR;
341  }
342  for (n=0;n<num_edges;n++)
343  total += ntohs (edges[n].token_length);
344  if (size != total)
345  {
346  fprintf (stderr, "Expected %u, got %u\n",
347  (unsigned int) size,
348  (unsigned int) total);
349  GNUNET_break_op (0);
350  return GNUNET_SYSERR;
351  }
352  off = len;
354  "Start iterating block of size %u, proof %u, off %u edges %u\n",
355  size, len, off, n);
356  /* &aux[off] always points to our token */
357  for (n=0;n<num_edges;n++)
358  {
360  "Edge %u/%u, off %u tokenlen %u (%.*s)\n",
361  n+1, num_edges, off,
362  ntohs (edges[n].token_length), ntohs (edges[n].token_length),
363  &aux[off]);
364  if (NULL != iterator)
365  if (GNUNET_NO == iterator (iter_cls,
366  &aux[off],
367  ntohs (edges[n].token_length),
368  &destinations[ntohs (edges[n].destination_index)]))
369  return GNUNET_OK;
370  off += ntohs (edges[n].token_length);
371  }
372  return GNUNET_OK;
373 }
374 
375 
386 struct RegexBlock *
388  unsigned int num_edges,
389  const struct REGEX_BLOCK_Edge *edges,
390  int accepting,
391  size_t *rsize)
392 {
393  struct RegexBlock *block;
394  struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
395  uint16_t destination_indices[num_edges];
396  struct GNUNET_HashCode *dests;
397  struct EdgeInfo *edgeinfos;
398  size_t off;
399  size_t len;
400  size_t total;
401  size_t slen;
402  unsigned int unique_destinations;
403  unsigned int j;
404  unsigned int i;
405  char *aux;
406 
407  len = strlen (proof);
408  if (len > UINT16_MAX)
409  {
410  GNUNET_break (0);
411  return NULL;
412  }
413  unique_destinations = 0;
414  total = sizeof (struct RegexBlock) + len;
415  for (i=0;i<num_edges;i++)
416  {
417  slen = strlen (edges[i].label);
418  if (slen > UINT16_MAX)
419  {
420  GNUNET_break (0);
421  return NULL;
422  }
423  total += slen;
424  for (j=0;j<unique_destinations;j++)
425  if (0 == memcmp (&destinations[j],
426  &edges[i].destination,
427  sizeof (struct GNUNET_HashCode)))
428  break;
429  if (j >= 1024)
430  {
431  GNUNET_break (0);
432  return NULL;
433  }
434  destination_indices[i] = j;
435  if (j == unique_destinations)
436  destinations[unique_destinations++] = edges[i].destination;
437  }
438  total += num_edges * sizeof (struct EdgeInfo) + unique_destinations * sizeof (struct GNUNET_HashCode);
439  if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
440  {
441  GNUNET_break (0);
442  return NULL;
443  }
444  block = GNUNET_malloc (total);
445  block->proof_len = htons (len);
446  block->is_accepting = htons (accepting);
447  block->num_edges = htons (num_edges);
448  block->num_destinations = htons (unique_destinations);
449  dests = (struct GNUNET_HashCode *) &block[1];
450  GNUNET_memcpy (dests, destinations, sizeof (struct GNUNET_HashCode) * unique_destinations);
451  edgeinfos = (struct EdgeInfo *) &dests[unique_destinations];
452  aux = (char *) &edgeinfos[num_edges];
453  off = len;
454  GNUNET_memcpy (aux, proof, len);
455  for (i=0;i<num_edges;i++)
456  {
457  slen = strlen (edges[i].label);
458  edgeinfos[i].token_length = htons ((uint16_t) slen);
459  edgeinfos[i].destination_index = htons (destination_indices[i]);
460  GNUNET_memcpy (&aux[off],
461  edges[i].label,
462  slen);
463  off += slen;
464  }
465  *rsize = total;
466  return block;
467 }
468 
469 
470 /* end of regex_block_lib.c */
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
GNUNET_NETWORK_STRUCT_END int GNUNET_BLOCK_is_accepting(const struct RegexBlock *block, size_t size)
Test if this block is marked as being an accept state.
int(* REGEX_INTERNAL_EgdeIterator)(void *cls, const char *token, size_t len, const struct GNUNET_HashCode *key)
Iterator over edges in a block.
struct GNUNET_HashCode destination
Destionation of the edge.
uint16_t destination_index
Index of the destination of this edge in the unique destinations array.
Struct to keep track of the xquery while iterating all the edges in a block.
uint16_t num_edges
Number of edges parting from this state.
int REGEX_BLOCK_get_key(const struct RegexBlock *block, size_t block_len, struct GNUNET_HashCode *key)
Obtain the key that a particular block is to be stored under.
int REGEX_BLOCK_iterate(const struct RegexBlock *block, size_t size, REGEX_INTERNAL_EgdeIterator iterator, void *iter_cls)
Iterate over all edges of a block of a regex state.
Block to announce a regex state.
int found
Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
#define GNUNET_NO
Definition: gnunet_common.h:81
#define LOG(kind,...)
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:78
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
Edge representation.
#define GNUNET_NETWORK_STRUCT_BEGIN
Define as empty, GNUNET_PACKED should suffice, but this won&#39;t work on W32.
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
uint16_t num_destinations
Nubmer of unique destinations reachable from this state.
uint16_t proof_len
Length of the proof regex string.
#define GNUNET_memcpy(dst, src, n)
static uint64_t proof
Definition: gnunet-scrypt.c:41
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:44
A 512-bit hashcode.
uint16_t token_length
Number of bytes the token for this edge takes in the token area.
static int res
Information for each edge.
struct RegexBlock * REGEX_BLOCK_create(const char *proof, unsigned int num_edges, const struct REGEX_BLOCK_Edge *edges, int accepting, size_t *rsize)
Construct a regex block to be stored in the DHT.
struct GNUNET_HashCode key
The key used in the DHT.
#define GNUNET_SYSERR
Definition: gnunet_common.h:79
static unsigned int size
Size of the "table".
Definition: peer.c:67
#define GNUNET_CONSTANTS_MAX_BLOCK_SIZE
Largest block that can be stored in the DHT.
int REGEX_BLOCK_check_proof(const char *proof, size_t proof_len, const struct GNUNET_HashCode *key)
Check if the given &#39;proof&#39; matches the given &#39;key&#39;.
const char * xquery
Xquery: string we are looking for.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_NETWORK_STRUCT_END
Define as empty, GNUNET_PACKED should suffice, but this won&#39;t work on W32;.
#define GNUNET_PACKED
gcc-ism to get packed structs.
int GNUNET_CRYPTO_hash_cmp(const struct GNUNET_HashCode *h1, const struct GNUNET_HashCode *h2)
Compare function for HashCodes, producing a total ordering of all hashcodes.
Definition: crypto_hash.c:278
common function to manipulate blocks stored by regex in the DHT
static int check_edge(void *cls, const char *token, size_t len, const struct GNUNET_HashCode *key)
Iterator over all edges in a block, checking for a presence of a given query.
#define GNUNET_log(kind,...)
#define GNUNET_YES
Definition: gnunet_common.h:80
int16_t is_accepting
Is this state an accepting state?
int REGEX_BLOCK_check(const struct RegexBlock *block, size_t size, const struct GNUNET_HashCode *query, const char *xquery)
Check if the regex block is well formed, including all edges.
#define GNUNET_malloc(size)
Wrapper around malloc.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...