X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fregex%2Fregex_block_lib.c;h=782827d5db0424782f393d9557293fe01f3410d8;hb=f1ca38573f22205e28ac482efebe463696c9c2c7;hp=01c591caa0a310289ee582bf2f5640bbe6b8c5e3;hpb=7706f0a08b2425622121c23a7d2054794f2d677c;p=oweals%2Fgnunet.git diff --git a/src/regex/regex_block_lib.c b/src/regex/regex_block_lib.c index 01c591caa..782827d5d 100644 --- a/src/regex/regex_block_lib.c +++ b/src/regex/regex_block_lib.c @@ -25,9 +25,92 @@ */ #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'. @@ -35,8 +118,7 @@ * @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. + * @return #GNUNET_OK if the proof is valid for the given key. */ int REGEX_BLOCK_check_proof (const char *proof, @@ -81,7 +163,7 @@ struct CheckEdgeContext * @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 @@ -92,7 +174,7 @@ check_edge (void *cls, { 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, GNUNET_h2s(key)); if (NULL == ctx->xquery) @@ -113,10 +195,9 @@ check_edge (void *cls, * @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. - * - * @return GNUNET_OK in case it's fine. - * GNUNET_NO in case the xquery exists and is not found (IRRELEVANT). - * GNUNET_SYSERR if the block is invalid. + * @return #GNUNET_OK in case it's fine. + * #GNUNET_NO in case the xquery exists and is not found (IRRELEVANT). + * #GNUNET_SYSERR if the block is invalid. */ int REGEX_BLOCK_check (const struct RegexBlock *block, @@ -124,27 +205,34 @@ REGEX_BLOCK_check (const struct RegexBlock *block, const struct GNUNET_HashCode *query, const char *xquery) { + struct GNUNET_HashCode key; struct CheckEdgeContext ctx; int res; - uint16_t len; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Checking block with xquery `%s'\n", - NULL != xquery ? xquery : "NULL"); - len = ntohs (block->proof_len); - if (size < sizeof (struct RegexBlock) + len) + 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 (GNUNET_OK != REGEX_BLOCK_check_proof ((const char *) &block[1], len, query)) + 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; res = REGEX_BLOCK_iterate (block, size, &check_edge, &ctx); @@ -152,6 +240,7 @@ REGEX_BLOCK_check (const struct RegexBlock *block, return GNUNET_SYSERR; if (NULL == xquery) return GNUNET_YES; + LOG (GNUNET_ERROR_TYPE_DEBUG, "Result %d\n", ctx.found); return ctx.found; } @@ -161,23 +250,38 @@ REGEX_BLOCK_check (const struct RegexBlock *block, * * @param block block to get the key from * @param block_len number of bytes in block - * @param query where to store the key - * @return GNUNET_OK on success, GNUNET_SYSERR if the block is malformed + * @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) + 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); - if (block_len < sizeof (struct RegexBlock) + 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 (&block[1], len, key); + GNUNET_CRYPTO_hash (&edges[num_edges], len, key); return GNUNET_OK; } @@ -186,14 +290,13 @@ REGEX_BLOCK_get_key (const struct RegexBlock *block, * Iterate over all edges of a block of a regex state. * * @param block Block to iterate over. - * @param size Size of block. + * @param size Size of @a block. * @param iterator Function to call on each edge in the block. - * @param iter_cls Closure for the iterator. - * - * @return GNUNET_SYSERR if an error has been encountered. - * GNUNET_OK if no error has been encountered. + * @param iter_cls Closure for the @a iterator. + * @return #GNUNET_SYSERR if an error has been encountered. + * #GNUNET_OK if no error has been encountered. * Note that if the iterator stops the iteration by returning - * GNUNET_NO, the block will no longer be checked for further errors. + * #GNUNET_NO, the block will no longer be checked for further errors. * The return value will be GNUNET_OK meaning that no errors were * found until the edge last notified to the iterator, but there might * be errors in further edges. @@ -204,69 +307,63 @@ REGEX_BLOCK_iterate (const struct RegexBlock *block, 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 = ntohs (block->proof_len); - 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;nproof_len), 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= 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; } @@ -290,50 +387,78 @@ REGEX_BLOCK_create (const char *proof, 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); if (len > UINT16_MAX) + { + GNUNET_break (0); + return NULL; + } + unique_destinations = 0; + total = sizeof (struct RegexBlock) + len; + for (i=0;i UINT16_MAX) + { + GNUNET_break (0); + return NULL; + } + total += slen; + for (j=0;j= 1024) { GNUNET_break (0); return NULL; } - size = sizeof (struct RegexBlock) + len; - block = GNUNET_malloc (size); + 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->n_edges = htonl (num_edges); block->is_accepting = htons (accepting); - - /* Store the proof at the end of the block. */ - aux = (char *) &block[1]; + 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;ikey = 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; }