*/
#include "platform.h"
#include "regex_block_lib.h"
+#include "gnunet_constants.h"
#define LOG(kind,...) GNUNET_log_from (kind,"regex-bck",__VA_ARGS__)
+GNUNET_NETWORK_STRUCT_BEGIN
+
+/**
+ * Information for each edge.
+ */
+struct EdgeInfo
+{
+ /**
+ * Index of the destination of this edge in the
+ * unique destinations array.
+ */
+ uint16_t destination_index GNUNET_PACKED;
+
+ /**
+ * Number of bytes the token for this edge takes in the
+ * token area.
+ */
+ uint16_t token_length GNUNET_PACKED;
+};
+
+
+/**
+ * @brief Block to announce a regex state.
+ */
+struct RegexBlock
+{
+
+ /**
+ * Length of the proof regex string.
+ */
+ uint16_t proof_len GNUNET_PACKED;
+
+ /**
+ * Is this state an accepting state?
+ */
+ int16_t is_accepting GNUNET_PACKED;
+
+ /**
+ * Number of edges parting from this state.
+ */
+ uint16_t num_edges GNUNET_PACKED;
+
+ /**
+ * Nubmer of unique destinations reachable from this state.
+ */
+ uint16_t num_destinations GNUNET_PACKED;
+
+ /* followed by 'struct GNUNET_HashCode[num_destinations]' */
+
+ /* followed by 'struct EdgeInfo[edge_destination_indices]' */
+
+ /* followed by 'char proof[n_proof]', NOT 0-terminated */
+
+ /* followed by 'char tokens[num_edges][edge_info[k].token_length]';
+ essentially all of the tokens one after the other in the
+ order of the edges; tokens are NOT 0-terminated */
+
+};
+
+
+GNUNET_NETWORK_STRUCT_END
+
+
+/**
+ * Test if this block is marked as being an accept state.
+ *
+ * @param block block to test
+ * @param size number of bytes in block
+ * @return GNUNET_YES if the block is accepting, GNUNET_NO if not
+ */
+int
+GNUNET_BLOCK_is_accepting (const struct RegexBlock *block,
+ size_t size)
+{
+ if (size < sizeof (struct RegexBlock))
+ {
+ GNUNET_break_op (0);
+ return GNUNET_SYSERR;
+ }
+ return ntohs (block->is_accepting);
+}
+
+
+/**
+ * Check if the given 'proof' matches the given 'key'.
+ *
+ * @param proof partial regex of a state
+ * @param proof_len number of bytes in 'proof'
+ * @param key hash of a state.
+ *
+ * @return GNUNET_OK if the proof is valid for the given key.
+ */
+int
+REGEX_BLOCK_check_proof (const char *proof,
+ size_t proof_len,
+ const struct GNUNET_HashCode *key)
+{
+ struct GNUNET_HashCode key_check;
+
+ if ( (NULL == proof) || (NULL == key))
+ {
+ GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Proof check failed, was NULL.\n");
+ return GNUNET_NO;
+ }
+ GNUNET_CRYPTO_hash (proof, proof_len, &key_check);
+ return (0 ==
+ GNUNET_CRYPTO_hash_cmp (key, &key_check)) ? GNUNET_OK : GNUNET_NO;
+}
+
+
/**
* Struct to keep track of the xquery while iterating all the edges in a block.
*/
*/
int found;
- /**
- * Key of the block we are iterating (for debug purposes).
- */
- char *key;
};
* @param token Token that follows to next state.
* @param len Lenght of token.
* @param key Hash of next state.
- *
+ *
* @return GNUNET_YES, to keep iterating
*/
static int
{
struct CheckEdgeContext *ctx = cls;
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+ GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
"edge %.*s [%u]: %s->%s\n",
- (int) len, token, len, ctx->key, GNUNET_h2s(key));
+ (int) len, token, len, GNUNET_h2s(key));
if (NULL == ctx->xquery)
return GNUNET_YES;
if (strlen (ctx->xquery) < len)
*
* @param block The start of the block.
* @param size The size of the block.
+ * @param query the query for the block
* @param xquery String describing the edge we are looking for.
* Can be NULL in case this is a put block.
*
int
REGEX_BLOCK_check (const struct RegexBlock *block,
size_t size,
+ const struct GNUNET_HashCode *query,
const char *xquery)
{
+ struct GNUNET_HashCode key;
struct CheckEdgeContext ctx;
int res;
- // FIXME: fails to check the proof!
- GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
- "Checking block with xquery `%s'\n",
- NULL != xquery ? xquery : "NULL");
- if ( (GNUNET_YES == ntohl (block->accepting)) &&
+ LOG (GNUNET_ERROR_TYPE_DEBUG, "Block check\n");
+ if (GNUNET_OK !=
+ REGEX_BLOCK_get_key (block, size,
+ &key))
+ {
+ GNUNET_break_op (0);
+ return GNUNET_SYSERR;
+ }
+ if (NULL != query &&
+ 0 != memcmp (&key,
+ query,
+ sizeof (struct GNUNET_HashCode)))
+ {
+ GNUNET_break_op (0);
+ return GNUNET_SYSERR;
+ }
+ if ( (GNUNET_YES == ntohs (block->is_accepting)) &&
( (NULL == xquery) || ('\0' == xquery[0]) ) )
+ {
+ LOG (GNUNET_ERROR_TYPE_DEBUG,
+ " out! Is accepting: %u, xquery %p\n",
+ ntohs(block->is_accepting), xquery);
return GNUNET_OK;
+ }
ctx.xquery = xquery;
ctx.found = GNUNET_NO;
- ctx.key = GNUNET_strdup (GNUNET_h2s (&block->key));
res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx);
- GNUNET_free (ctx.key);
if (GNUNET_SYSERR == res)
return GNUNET_SYSERR;
if (NULL == xquery)
return GNUNET_YES;
+ LOG (GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found);
return ctx.found;
}
+/**
+ * Obtain the key that a particular block is to be stored under.
+ *
+ * @param block block to get the key from
+ * @param block_len number of bytes in block
+ * @param key where to store the key
+ * @return GNUNET_OK on success, GNUNET_SYSERR if the block is malformed
+ */
+int
+REGEX_BLOCK_get_key (const struct RegexBlock *block,
+ size_t block_len,
+ struct GNUNET_HashCode *key)
+{
+ uint16_t len;
+ const struct GNUNET_HashCode *destinations;
+ const struct EdgeInfo *edges;
+ uint16_t num_destinations;
+ uint16_t num_edges;
+ size_t total;
+
+ if (block_len < sizeof (struct RegexBlock))
+ {
+ GNUNET_break_op (0);
+ return GNUNET_SYSERR;
+ }
+ num_destinations = ntohs (block->num_destinations);
+ num_edges = ntohs (block->num_edges);
+ len = ntohs (block->proof_len);
+ destinations = (const struct GNUNET_HashCode *) &block[1];
+ edges = (const struct EdgeInfo *) &destinations[num_destinations];
+ total = sizeof (struct RegexBlock) + num_destinations * sizeof (struct GNUNET_HashCode) + num_edges + sizeof (struct EdgeInfo) + len;
+ if (block_len < total)
+ {
+ GNUNET_break_op (0);
+ return GNUNET_SYSERR;
+ }
+ GNUNET_CRYPTO_hash (&edges[num_edges], len, key);
+ return GNUNET_OK;
+}
+
+
/**
* Iterate over all edges of a block of a regex state.
*
*/
int
REGEX_BLOCK_iterate (const struct RegexBlock *block,
- size_t size,
- REGEX_INTERNAL_EgdeIterator iterator,
- void *iter_cls)
+ size_t size,
+ REGEX_INTERNAL_EgdeIterator iterator,
+ void *iter_cls)
{
- struct RegexEdge *edge;
+ uint16_t len;
+ const struct GNUNET_HashCode *destinations;
+ const struct EdgeInfo *edges;
+ const char *aux;
+ uint16_t num_destinations;
+ uint16_t num_edges;
+ size_t total;
unsigned int n;
- unsigned int n_token;
- unsigned int i;
- size_t offset;
- char *aux;
+ size_t off;
- offset = sizeof (struct RegexBlock);
- if (offset >= size) /* Is it safe to access the regex block? */
+ LOG (GNUNET_ERROR_TYPE_DEBUG, "Block iterate\n");
+ if (size < sizeof (struct RegexBlock))
{
GNUNET_break_op (0);
return GNUNET_SYSERR;
}
- n = ntohl (block->n_proof);
- offset += n;
- if (offset >= size) /* Is it safe to access the regex proof? */
+ num_destinations = ntohs (block->num_destinations);
+ num_edges = ntohs (block->num_edges);
+ len = ntohs (block->proof_len);
+ destinations = (const struct GNUNET_HashCode *) &block[1];
+ edges = (const struct EdgeInfo *) &destinations[num_destinations];
+ aux = (const char *) &edges[num_edges];
+ total = sizeof (struct RegexBlock) + num_destinations * sizeof (struct GNUNET_HashCode) + num_edges * sizeof (struct EdgeInfo) + len;
+ if (size < total)
{
GNUNET_break_op (0);
return GNUNET_SYSERR;
}
- aux = (char *) &block[1]; /* Skip regex block */
- aux = &aux[n]; /* Skip regex proof */
- n = ntohl (block->n_edges);
+ for (n=0;n<num_edges;n++)
+ total += ntohs (edges[n].token_length);
+ if (size != total)
+ {
+ fprintf (stderr, "Expected %u, got %u\n",
+ (unsigned int) size,
+ (unsigned int) total);
+ GNUNET_break_op (0);
+ return GNUNET_SYSERR;
+ }
+ off = len;
LOG (GNUNET_ERROR_TYPE_DEBUG,
"Start iterating block of size %u, proof %u, off %u edges %u\n",
- size, ntohl (block->n_proof), offset, n);
- /* aux always points at the end of the previous block */
- for (i = 0; i < n; i++)
+ size, len, off, n);
+ /* &aux[off] always points to our token */
+ for (n=0;n<num_edges;n++)
{
- offset += sizeof (struct RegexEdge);
- LOG (GNUNET_ERROR_TYPE_DEBUG, "* Edge %u, off %u\n", i, offset);
- if (offset >= size) /* Is it safe to access the next edge block? */
- {
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "* Size not enough for RegexEdge, END\n");
- GNUNET_break_op (0);
- return GNUNET_SYSERR;
- }
- edge = (struct RegexEdge *) aux;
- n_token = ntohl (edge->n_token);
- offset += n_token;
- LOG (GNUNET_ERROR_TYPE_DEBUG,
- "* Token length %u, off %u\n", n_token, offset);
- if (offset > size) /* Is it safe to access the edge token? */
- {
- LOG (GNUNET_ERROR_TYPE_WARNING,
- "* Size not enough for edge token, END\n");
- GNUNET_break_op (0);
- return GNUNET_SYSERR;
- }
- aux = (char *) &edge[1]; /* Skip edge block */
+ LOG (GNUNET_ERROR_TYPE_DEBUG,
+ " Edge %u/%u, off %u tokenlen %u (%.*s)\n", n+1, num_edges, off,
+ ntohs (edges[n].token_length), ntohs (edges[n].token_length),
+ &aux[off]);
if (NULL != iterator)
- if (GNUNET_NO == iterator (iter_cls, aux, n_token, &edge->key))
- return GNUNET_OK;
- aux = &aux[n_token]; /* Skip edge token */
- }
- /* The total size should be exactly the size of (regex + all edges) blocks
- * If size == -1, block is from cache and therefore previously checked and
- * assumed correct. */
- if ( (offset != size) && (SIZE_MAX != size) )
- {
- GNUNET_break_op (0);
- return GNUNET_SYSERR;
+ if (GNUNET_NO == iterator (iter_cls,
+ &aux[off],
+ ntohs (edges[n].token_length),
+ &destinations[ntohs (edges[n].destination_index)]))
+ return GNUNET_OK;
+ off += ntohs (edges[n].token_length);
}
return GNUNET_OK;
}
* @param proof proof string for the block
* @param num_edges number of edges in the block
* @param edges the edges of the block
- * @return the regex block
+ * @param accepting is this an accepting state
+ * @param rsize set to the size of the returned block (OUT-only)
+ * @return the regex block, NULL on error
*/
struct RegexBlock *
-REGEX_BLOCK_create (const struct GNUNET_HashCode *key,
- const char *proof,
- unsigned int num_edges,
- const struct REGEX_BLOCK_Edge *edges,
- int accepting,
- size_t *rsize)
+REGEX_BLOCK_create (const char *proof,
+ unsigned int num_edges,
+ const struct REGEX_BLOCK_Edge *edges,
+ int accepting,
+ size_t *rsize)
{
struct RegexBlock *block;
- struct RegexEdge *block_edge;
- size_t size;
+ struct GNUNET_HashCode destinations[1024]; /* 1024 = 64k/64 bytes/key == absolute MAX */
+ uint16_t destination_indices[num_edges];
+ struct GNUNET_HashCode *dests;
+ struct EdgeInfo *edgeinfos;
+ size_t off;
size_t len;
+ size_t total;
+ size_t slen;
+ unsigned int unique_destinations;
+ unsigned int j;
unsigned int i;
- unsigned int offset;
char *aux;
- len = strlen(proof);
- size = sizeof (struct RegexBlock) + len;
- block = GNUNET_malloc (size);
- block->key = *key;
- block->n_proof = htonl (len);
- block->n_edges = htonl (num_edges);
- block->accepting = htonl (accepting);
-
- /* Store the proof at the end of the block. */
- aux = (char *) &block[1];
+ len = strlen (proof);
+ if (len > UINT16_MAX)
+ {
+ GNUNET_break (0);
+ return NULL;
+ }
+ unique_destinations = 0;
+ total = sizeof (struct RegexBlock) + len;
+ for (i=0;i<num_edges;i++)
+ {
+ slen = strlen (edges[i].label);
+ if (slen > UINT16_MAX)
+ {
+ GNUNET_break (0);
+ return NULL;
+ }
+ total += slen;
+ for (j=0;j<unique_destinations;j++)
+ if (0 == memcmp (&destinations[j],
+ &edges[i].destination,
+ sizeof (struct GNUNET_HashCode)))
+ break;
+ if (j >= 1024)
+ {
+ GNUNET_break (0);
+ return NULL;
+ }
+ destination_indices[i] = j;
+ if (j == unique_destinations)
+ destinations[unique_destinations++] = edges[i].destination;
+ }
+ total += num_edges * sizeof (struct EdgeInfo) + unique_destinations * sizeof (struct GNUNET_HashCode);
+ if (total >= GNUNET_CONSTANTS_MAX_BLOCK_SIZE)
+ {
+ GNUNET_break (0);
+ return NULL;
+ }
+ block = GNUNET_malloc (total);
+ block->proof_len = htons (len);
+ block->is_accepting = htons (accepting);
+ block->num_edges = htons (num_edges);
+ block->num_destinations = htons (unique_destinations);
+ dests = (struct GNUNET_HashCode *) &block[1];
+ memcpy (dests, destinations, sizeof (struct GNUNET_HashCode) * unique_destinations);
+ edgeinfos = (struct EdgeInfo *) &dests[unique_destinations];
+ aux = (char *) &edgeinfos[num_edges];
+ off = len;
memcpy (aux, proof, len);
- aux = &aux[len];
-
- /* Store each edge in a variable length MeshEdge struct at the
- * very end of the MeshRegexBlock structure.
- */
- for (i = 0; i < num_edges; i++)
+ for (i=0;i<num_edges;i++)
{
- /* aux points at the end of the last block */
- len = strlen (edges[i].label);
- size += sizeof (struct RegexEdge) + len;
- // Calculate offset FIXME is this ok? use size instead?
- offset = aux - (char *) block;
- block = GNUNET_realloc (block, size);
- aux = &((char *) block)[offset];
- block_edge = (struct RegexEdge *) aux;
- block_edge->key = edges[i].destination;
- block_edge->n_token = htonl (len);
- aux = (char *) &block_edge[1];
- memcpy (aux, edges[i].label, len);
- aux = &aux[len];
+ slen = strlen (edges[i].label);
+ edgeinfos[i].token_length = htons ((uint16_t) slen);
+ edgeinfos[i].destination_index = htons (destination_indices[i]);
+ memcpy (&aux[off],
+ edges[i].label,
+ slen);
+ off += slen;
}
- *rsize = size;
+ *rsize = total;
return block;
}
projects / oweals / gnunet.git / blobdiff