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 {
43 
49 };
50 
51 
55 struct RegexBlock {
59  uint16_t proof_len GNUNET_PACKED;
60 
64  int16_t is_accepting GNUNET_PACKED;
65 
69  uint16_t num_edges GNUNET_PACKED;
70 
74  uint16_t num_destinations GNUNET_PACKED;
75 
76  /* followed by 'struct GNUNET_HashCode[num_destinations]' */
77 
78  /* followed by 'struct EdgeInfo[edge_destination_indices]' */
79 
80  /* followed by 'char proof[n_proof]', NOT 0-terminated */
81 
82  /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
83  essentially all of the tokens one after the other in the
84  order of the edges; tokens are NOT 0-terminated */
85 };
86 
87 
89 
90 
98 int
100  size_t size)
101 {
102  if (size < sizeof(struct RegexBlock))
103  {
104  GNUNET_break_op(0);
105  return GNUNET_SYSERR;
106  }
107  return ntohs(block->is_accepting);
108 }
109 
110 
119 int
121  size_t proof_len,
122  const struct GNUNET_HashCode *key)
123 {
124  struct GNUNET_HashCode key_check;
125 
126  if ((NULL == proof) || (NULL == key))
127  {
128  GNUNET_log(GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
129  return GNUNET_NO;
130  }
131  GNUNET_CRYPTO_hash(proof, proof_len, &key_check);
132  return (0 ==
133  GNUNET_CRYPTO_hash_cmp(key, &key_check)) ? GNUNET_OK : GNUNET_NO;
134 }
135 
136 
144  const char *xquery;
145 
149  int found;
150 };
151 
152 
163 static int
164 check_edge(void *cls,
165  const char *token,
166  size_t len,
167  const struct GNUNET_HashCode *key)
168 {
169  struct CheckEdgeContext *ctx = cls;
170 
172  "edge %.*s [%u]: %s\n",
173  (int)len,
174  token,
175  (unsigned int)len,
176  GNUNET_h2s(key));
177  if (NULL == ctx->xquery)
178  return GNUNET_YES;
179  if (strlen(ctx->xquery) < len)
180  return GNUNET_YES; /* too long */
181  if (0 == strncmp(ctx->xquery, token, len))
182  ctx->found = GNUNET_OK;
183  return GNUNET_YES; /* keep checking for malformed data! */
184 }
185 
186 
199 int
200 REGEX_BLOCK_check(const struct RegexBlock *block,
201  size_t size,
202  const struct GNUNET_HashCode *query,
203  const char *xquery)
204 {
205  struct GNUNET_HashCode key;
206  struct CheckEdgeContext ctx;
207  int res;
208 
210  "Block check\n");
211  if (GNUNET_OK !=
212  REGEX_BLOCK_get_key(block, size,
213  &key))
214  {
215  GNUNET_break_op(0);
216  return GNUNET_SYSERR;
217  }
218  if (NULL != query &&
219  0 != GNUNET_memcmp(&key,
220  query))
221  {
222  GNUNET_break_op(0);
223  return GNUNET_SYSERR;
224  }
225  if ((GNUNET_YES == ntohs(block->is_accepting)) &&
226  ((NULL == xquery) || ('\0' == xquery[0])))
227  {
229  " out! Is accepting: %u, xquery %p\n",
230  ntohs(block->is_accepting),
231  xquery);
232  return GNUNET_OK;
233  }
234  ctx.xquery = xquery;
235  ctx.found = GNUNET_NO;
236  res = REGEX_BLOCK_iterate(block, size, &check_edge, &ctx);
237  if (GNUNET_SYSERR == res)
238  return GNUNET_SYSERR;
239  if (NULL == xquery)
240  return GNUNET_YES;
241  LOG(GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
242  return ctx.found;
243 }
244 
245 
254 int
255 REGEX_BLOCK_get_key(const struct RegexBlock *block,
256  size_t block_len,
257  struct GNUNET_HashCode *key)
258 {
259  uint16_t len;
260  const struct GNUNET_HashCode *destinations;
261  const struct EdgeInfo *edges;
262  uint16_t num_destinations;
263  uint16_t num_edges;
264  size_t total;
265 
266  if (block_len < sizeof(struct RegexBlock))
267  {
268  GNUNET_break_op(0);
269  return GNUNET_SYSERR;
270  }
271  num_destinations = ntohs(block->num_destinations);
272  num_edges = ntohs(block->num_edges);
273  len = ntohs(block->proof_len);
274  destinations = (const struct GNUNET_HashCode *)&block[1];
275  edges = (const struct EdgeInfo *)&destinations[num_destinations];
276  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct GNUNET_HashCode) + num_edges * sizeof(struct EdgeInfo) + len;
277  if (block_len < total)
278  {
279  GNUNET_break_op(0);
280  return GNUNET_SYSERR;
281  }
282  GNUNET_CRYPTO_hash(&edges[num_edges], len, key);
283  return GNUNET_OK;
284 }
285 
286 
302 int
303 REGEX_BLOCK_iterate(const struct RegexBlock *block,
304  size_t size,
306  void *iter_cls)
307 {
308  uint16_t len;
309  const struct GNUNET_HashCode *destinations;
310  const struct EdgeInfo *edges;
311  const char *aux;
312  uint16_t num_destinations;
313  uint16_t num_edges;
314  size_t total;
315  unsigned int n;
316  size_t off;
317 
318  LOG(GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
319  if (size < sizeof(struct RegexBlock))
320  {
321  GNUNET_break_op(0);
322  return GNUNET_SYSERR;
323  }
324  num_destinations = ntohs(block->num_destinations);
325  num_edges = ntohs(block->num_edges);
326  len = ntohs(block->proof_len);
327  destinations = (const struct GNUNET_HashCode *)&block[1];
328  edges = (const struct EdgeInfo *)&destinations[num_destinations];
329  aux = (const char *)&edges[num_edges];
330  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct GNUNET_HashCode) + num_edges * sizeof(struct EdgeInfo) + len;
331  if (size < total)
332  {
333  GNUNET_break_op(0);
334  return GNUNET_SYSERR;
335  }
336  for (n = 0; n < num_edges; n++)
337  total += ntohs(edges[n].token_length);
338  if (size != total)
339  {
340  fprintf(stderr, "Expected %u, got %u\n",
341  (unsigned int)size,
342  (unsigned int)total);
343  GNUNET_break_op(0);
344  return GNUNET_SYSERR;
345  }
346  off = len;
348  "Start iterating block of size %u, proof %u, off %u edges %u\n",
349  size, len, off, n);
350  /* &aux[off] always points to our token */
351  for (n = 0; n < num_edges; n++)
352  {
354  "Edge %u/%u, off %u tokenlen %u (%.*s)\n",
355  n + 1, num_edges, off,
356  ntohs(edges[n].token_length), ntohs(edges[n].token_length),
357  &aux[off]);
358  if (NULL != iterator)
359  if (GNUNET_NO == iterator(iter_cls,
360  &aux[off],
361  ntohs(edges[n].token_length),
362  &destinations[ntohs(edges[n].destination_index)]))
363  return GNUNET_OK;
364  off += ntohs(edges[n].token_length);
365  }
366  return GNUNET_OK;
367 }
368 
369 
380 struct RegexBlock *
382  unsigned int num_edges,
383  const struct REGEX_BLOCK_Edge *edges,
384  int accepting,
385  size_t *rsize)
386 {
387  struct RegexBlock *block;
388  struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
389  uint16_t destination_indices[num_edges];
390  struct GNUNET_HashCode *dests;
391  struct EdgeInfo *edgeinfos;
392  size_t off;
393  size_t len;
394  size_t total;
395  size_t slen;
396  unsigned int unique_destinations;
397  unsigned int j;
398  unsigned int i;
399  char *aux;
400 
401  len = strlen(proof);
402  if (len > UINT16_MAX)
403  {
404  GNUNET_break(0);
405  return NULL;
406  }
407  unique_destinations = 0;
408  total = sizeof(struct RegexBlock) + len;
409  for (i = 0; i < num_edges; i++)
410  {
411  slen = strlen(edges[i].label);
412  if (slen > UINT16_MAX)
413  {
414  GNUNET_break(0);
415  return NULL;
416  }
417  total += slen;
418  for (j = 0; j < unique_destinations; j++)
419  if (0 == memcmp(&destinations[j],
420  &edges[i].destination,
421  sizeof(struct GNUNET_HashCode)))
422  break;
423  if (j >= 1024)
424  {
425  GNUNET_break(0);
426  return NULL;
427  }
428  destination_indices[i] = j;
429  if (j == unique_destinations)
430  destinations[unique_destinations++] = edges[i].destination;
431  }
432  total += num_edges * sizeof(struct EdgeInfo) + unique_destinations * sizeof(struct GNUNET_HashCode);
433  if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
434  {
435  GNUNET_break(0);
436  return NULL;
437  }
438  block = GNUNET_malloc(total);
439  block->proof_len = htons(len);
440  block->is_accepting = htons(accepting);
441  block->num_edges = htons(num_edges);
442  block->num_destinations = htons(unique_destinations);
443  dests = (struct GNUNET_HashCode *)&block[1];
444  GNUNET_memcpy(dests, destinations, sizeof(struct GNUNET_HashCode) * unique_destinations);
445  edgeinfos = (struct EdgeInfo *)&dests[unique_destinations];
446  aux = (char *)&edgeinfos[num_edges];
447  off = len;
448  GNUNET_memcpy(aux, proof, len);
449  for (i = 0; i < num_edges; i++)
450  {
451  slen = strlen(edges[i].label);
452  edgeinfos[i].token_length = htons((uint16_t)slen);
453  edgeinfos[i].destination_index = htons(destination_indices[i]);
454  GNUNET_memcpy(&aux[off],
455  edges[i].label,
456  slen);
457  off += slen;
458  }
459  *rsize = total;
460  return block;
461 }
462 
463 
464 /* 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: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:76
static unsigned int size
Size of the "table".
Definition: peer.c:66
#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: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...