GNUnet  0.11.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 {
61  uint16_t proof_len GNUNET_PACKED;
62 
66  int16_t is_accepting GNUNET_PACKED;
67 
71  uint16_t num_edges GNUNET_PACKED;
72 
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 
91 
92 
100 int
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 
121 int
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 
143 {
147  const char *xquery;
148 
152  int found;
153 };
154 
155 
166 static int
167 check_edge (void *cls,
168  const char *token,
169  size_t len,
170  const struct GNUNET_HashCode *key)
171 {
172  struct CheckEdgeContext *ctx = cls;
173 
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 
202 int
203 REGEX_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 
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  {
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 
257 int
258 REGEX_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
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 
307 int
308 REGEX_BLOCK_iterate (const struct RegexBlock *block,
309  size_t size,
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
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;
355  "Start iterating block of size %u, proof %u, off %u edges %u\n",
356  size, len, off, n);
357  /* &aux[off] always points to our token */
358  for (n = 0; n < num_edges; n++)
359  {
361  "Edge %u/%u, off %u tokenlen %u (%.*s)\n",
362  n + 1, num_edges, 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 
388 struct RegexBlock *
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 */
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.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
int found
Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
#define GNUNET_NO
Definition: gnunet_common.h:78
#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:75
#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.
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:48
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:76
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:294
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:77
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...