GNUnet  0.20.0
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 {
62 
67 
72 
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 
113 int
115  size_t proof_len,
116  const struct GNUNET_HashCode *key)
117 {
118  struct GNUNET_HashCode key_check;
119 
120  if ((NULL == proof) || (NULL == key))
121  {
122  GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
123  return GNUNET_NO;
124  }
125  GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
126  return (0 ==
127  GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
128 }
129 
130 
135 {
139  const char *xquery;
140 
144  int found;
145 };
146 
147 
158 static int
159 check_edge (void *cls,
160  const char *token,
161  size_t len,
162  const struct GNUNET_HashCode *key)
163 {
164  struct CheckEdgeContext *ctx = cls;
165 
167  "edge %.*s [%u]: %s\n",
168  (int) len,
169  token,
170  (unsigned int) len,
171  GNUNET_h2s (key));
172  if (NULL == ctx->xquery)
173  return GNUNET_YES;
174  if (strlen (ctx->xquery) < len)
175  return GNUNET_YES; /* too long */
176  if (0 == strncmp (ctx->xquery, token, len))
177  ctx->found = GNUNET_OK;
178  return GNUNET_YES; /* keep checking for malformed data! */
179 }
180 
181 
182 int
183 REGEX_BLOCK_check (const struct RegexBlock *block,
184  size_t size,
185  const struct GNUNET_HashCode *query,
186  const char *xquery)
187 {
188  struct GNUNET_HashCode key;
189  struct CheckEdgeContext ctx;
190  int res;
191 
193  "Block check\n");
194  if (GNUNET_OK !=
195  REGEX_BLOCK_get_key (block, size,
196  &key))
197  {
198  GNUNET_break_op (0);
199  return GNUNET_SYSERR;
200  }
201  if ((NULL != query) &&
202  (0 != GNUNET_memcmp (&key,
203  query)) )
204  {
205  GNUNET_break_op (0);
206  return GNUNET_SYSERR;
207  }
208  if ((GNUNET_YES == ntohs (block->is_accepting)) &&
209  ((NULL == xquery) || ('\0' == xquery[0])))
210  {
212  " out! Is accepting: %u, xquery %p\n",
213  ntohs (block->is_accepting),
214  xquery);
215  return GNUNET_OK;
216  }
217  ctx.xquery = xquery;
218  ctx.found = GNUNET_NO;
219  res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
220  if (GNUNET_SYSERR == res)
221  return GNUNET_SYSERR;
222  if (NULL == xquery)
223  return GNUNET_YES;
224  LOG (GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
225  return ctx.found;
226 }
227 
228 
229 int
230 REGEX_BLOCK_get_key (const struct RegexBlock *block,
231  size_t block_len,
232  struct GNUNET_HashCode *key)
233 {
234  uint16_t len;
235  const struct GNUNET_HashCode *destinations;
236  const struct EdgeInfo *edges;
237  uint16_t num_destinations;
238  uint16_t num_edges;
239  size_t total;
240 
241  if (block_len < sizeof(struct RegexBlock))
242  {
243  GNUNET_break_op (0);
244  return GNUNET_SYSERR;
245  }
246  num_destinations = ntohs (block->num_destinations);
247  num_edges = ntohs (block->num_edges);
248  len = ntohs (block->proof_len);
249  destinations = (const struct GNUNET_HashCode *) &block[1];
250  edges = (const struct EdgeInfo *) &destinations[num_destinations];
251  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
253  + num_edges * sizeof(struct EdgeInfo) + len;
254  if (block_len < total)
255  {
256  GNUNET_break_op (0);
257  return GNUNET_SYSERR;
258  }
259  GNUNET_CRYPTO_hash (&edges[num_edges], len, key);
260  return GNUNET_OK;
261 }
262 
263 
264 int
265 REGEX_BLOCK_iterate (const struct RegexBlock *block,
266  size_t size,
268  void *iter_cls)
269 {
270  uint16_t len;
271  const struct GNUNET_HashCode *destinations;
272  const struct EdgeInfo *edges;
273  const char *aux;
274  uint16_t num_destinations;
275  uint16_t num_edges;
276  size_t total;
277  unsigned int n;
278  size_t off;
279 
280  LOG (GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
281  if (size < sizeof(struct RegexBlock))
282  {
283  GNUNET_break_op (0);
284  return GNUNET_SYSERR;
285  }
286  num_destinations = ntohs (block->num_destinations);
287  num_edges = ntohs (block->num_edges);
288  len = ntohs (block->proof_len);
289  destinations = (const struct GNUNET_HashCode *) &block[1];
290  edges = (const struct EdgeInfo *) &destinations[num_destinations];
291  aux = (const char *) &edges[num_edges];
292  total = sizeof(struct RegexBlock) + num_destinations * sizeof(struct
294  + num_edges * sizeof(struct EdgeInfo) + len;
295  if (size < total)
296  {
297  GNUNET_break_op (0);
298  return GNUNET_SYSERR;
299  }
300  for (n = 0; n < num_edges; n++)
301  total += ntohs (edges[n].token_length);
302  if (size != total)
303  {
304  fprintf (stderr, "Expected %u, got %u\n",
305  (unsigned int) size,
306  (unsigned int) total);
307  GNUNET_break_op (0);
308  return GNUNET_SYSERR;
309  }
310  off = len;
312  "Start iterating block of size %lu, proof %u, off %lu edges %u\n",
313  (unsigned long) size, len, (unsigned long) off, n);
314  /* &aux[off] always points to our token */
315  for (n = 0; n < num_edges; n++)
316  {
318  "Edge %u/%u, off %lu tokenlen %u (%.*s)\n",
319  n + 1, num_edges, (unsigned long) off,
320  ntohs (edges[n].token_length), ntohs (edges[n].token_length),
321  &aux[off]);
322  if (NULL != iterator)
323  if (GNUNET_NO == iterator (iter_cls,
324  &aux[off],
325  ntohs (edges[n].token_length),
326  &destinations[ntohs (
327  edges[n].destination_index)]))
328  return GNUNET_OK;
329  off += ntohs (edges[n].token_length);
330  }
331  return GNUNET_OK;
332 }
333 
334 
345 struct RegexBlock *
347  unsigned int num_edges,
348  const struct REGEX_BLOCK_Edge *edges,
349  int accepting,
350  size_t *rsize)
351 {
352  struct RegexBlock *block;
353  struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
354  uint16_t destination_indices[num_edges];
355  struct GNUNET_HashCode *dests;
356  struct EdgeInfo *edgeinfos;
357  size_t off;
358  size_t len;
359  size_t total;
360  size_t slen;
361  unsigned int unique_destinations;
362  unsigned int j;
363  unsigned int i;
364  char *aux;
365 
366  len = strlen (proof);
367  if (len > UINT16_MAX)
368  {
369  GNUNET_break (0);
370  return NULL;
371  }
372  unique_destinations = 0;
373  total = sizeof(struct RegexBlock) + len;
374  for (i = 0; i < num_edges; i++)
375  {
376  slen = strlen (edges[i].label);
377  if (slen > UINT16_MAX)
378  {
379  GNUNET_break (0);
380  return NULL;
381  }
382  total += slen;
383  for (j = 0; j < unique_destinations; j++)
384  if (0 == memcmp (&destinations[j],
385  &edges[i].destination,
386  sizeof(struct GNUNET_HashCode)))
387  break;
388  if (j >= 1024)
389  {
390  GNUNET_break (0);
391  return NULL;
392  }
393  destination_indices[i] = j;
394  if (j == unique_destinations)
395  destinations[unique_destinations++] = edges[i].destination;
396  }
397  total += num_edges * sizeof(struct EdgeInfo) + unique_destinations
398  * sizeof(struct GNUNET_HashCode);
399  if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
400  {
401  GNUNET_break (0);
402  return NULL;
403  }
404  block = GNUNET_malloc (total);
405  block->proof_len = htons (len);
406  block->is_accepting = htons (accepting);
407  block->num_edges = htons (num_edges);
408  block->num_destinations = htons (unique_destinations);
409  dests = (struct GNUNET_HashCode *) &block[1];
410  GNUNET_memcpy (dests, destinations, sizeof(struct GNUNET_HashCode)
411  * unique_destinations);
412  edgeinfos = (struct EdgeInfo *) &dests[unique_destinations];
413  aux = (char *) &edgeinfos[num_edges];
414  off = len;
415  GNUNET_memcpy (aux, proof, len);
416  for (i = 0; i < num_edges; i++)
417  {
418  slen = strlen (edges[i].label);
419  edgeinfos[i].token_length = htons ((uint16_t) slen);
420  edgeinfos[i].destination_index = htons (destination_indices[i]);
421  GNUNET_memcpy (&aux[off],
422  edges[i].label,
423  slen);
424  off += slen;
425  }
426  *rsize = total;
427  return block;
428 }
429 
430 
431 /* end of regex_block_lib.c */
static int res
struct GNUNET_HashCode key
The key used in the DHT.
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
static uint64_t proof
Definition: gnunet-scrypt.c:49
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
#define GNUNET_CONSTANTS_MAX_BLOCK_SIZE
Largest block that can be stored in the DHT.
void GNUNET_CRYPTO_hash(const void *block, size_t size, struct GNUNET_HashCode *ret)
Compute hash of a given block.
Definition: crypto_hash.c:41
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:221
static int iterator(void *cls, const struct GNUNET_PeerIdentity *key, void *value)
Iterator over hash map entries.
#define GNUNET_NETWORK_STRUCT_BEGIN
Define as empty, GNUNET_PACKED should suffice, but this won't work on W32.
#define GNUNET_log(kind,...)
#define GNUNET_NETWORK_STRUCT_END
Define as empty, GNUNET_PACKED should suffice, but this won't work on W32;.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_PACKED
gcc-ism to get packed structs.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
@ GNUNET_ERROR_TYPE_ERROR
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_malloc(size)
Wrapper around malloc.
static unsigned int size
Size of the "table".
Definition: peer.c:68
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.
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.
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.
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_check_proof(const char *proof, size_t proof_len, const struct GNUNET_HashCode *key)
Check if the given 'proof' matches the given 'key'.
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_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 LOG(kind,...)
common function to manipulate blocks stored by regex in the DHT
int(* REGEX_INTERNAL_EgdeIterator)(void *cls, const char *token, size_t len, const struct GNUNET_HashCode *key)
Iterator over edges in a block.
Struct to keep track of the xquery while iterating all the edges in a block.
const char * xquery
Xquery: string we are looking for.
int found
Has any edge matched the xquery so far? (GNUNET_OK / GNUNET_NO)
Information for each edge.
uint16_t destination_index
Index of the destination of this edge in the unique destinations array.
uint16_t token_length
Number of bytes the token for this edge takes in the token area.
A 512-bit hashcode.
Edge representation.
struct GNUNET_HashCode destination
Destination of the edge.
Block to announce a regex state.
uint16_t num_destinations
Number of unique destinations reachable from this state.
uint16_t proof_len
Length of the proof regex string.
int16_t is_accepting
Is this state an accepting state?
uint16_t num_edges
Number of edges parting from this state.