From 38300a8d3b441cc492adcd72d4a60b861eea0e95 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Mon, 22 Apr 2019 11:48:12 +0200 Subject: [PATCH] changing UUID types (in preparation for RTT tracking) --- src/transport/gnunet-service-tng.c | 137 ++++++++++++++++++++++++----- 1 file changed, 116 insertions(+), 21 deletions(-) diff --git a/src/transport/gnunet-service-tng.c b/src/transport/gnunet-service-tng.c index c4974ca23..a35357d9b 100644 --- a/src/transport/gnunet-service-tng.c +++ b/src/transport/gnunet-service-tng.c @@ -25,6 +25,21 @@ * TODO: * Implement next: * - track RTT, distance, loss, etc. => requires extra data structures! + * => fragment UUIDs should be 'sequential' 32-bit numbers, for cummulative + * acks with Bitmask + * => fragments carry their own offsets, so receiver will NOT require + * seeing all the possible values + * => can generate 'fresh' UUIDs for each retransmission to track it + * => but need to keep 'map' of 32-bit UUID to queue! + * => message UUIDs are currently overkill with 256 bits + * => cummulative acks for messages include full UUID list + * => message UUID size should be chosen to result in 8 byte alignment + * => could encode 32-bit counter + 32-bit queue UUID in 64-bit message + * UUID? + * => Use multihashmap32 on counter for lookup in hashmap? + * => FIXME: 2x32 bit introduced, but still set to random value + * instead of using the generators! + * (and generators not initialized to random starting values either) * - consider replacing random `struct GNUNET_ShortHashCode` message UUIDs * with (incrementing) 64-bit numbers (compacting both * `struct TransportReliabilityBox` and `struct @@ -260,9 +275,16 @@ GNUNET_NETWORK_STRUCT_BEGIN struct MessageUUIDP { /** - * Unique value. + * Unique value, generated by incrementing the + * `message_uuid_ctr` of `struct Neighbour`. */ - struct GNUNET_ShortHashCode uuid; // FIXME: change to 8 bytes + uint32_t uuid GNUNET_PACKED; + + /** + * UUID of the queue that was used to transmit this message. + * Used to map acknowledgements back to the respective queue. + */ + uint32_t queue_uuid GNUNET_PACKED; }; @@ -274,7 +296,7 @@ struct FragmentUUIDP /** * Unique value identifying a fragment, in NBO. */ - uint32_t uuid GNUNET_PACKED; // FIXME: change to 2x 2 bytes? + uint32_t uuid GNUNET_PACKED; }; @@ -1277,6 +1299,14 @@ struct Queue */ uint32_t qid; + /** + * UUID used to map acknowledgements back to the queue that + * was used for transmission. Note that @e queue_uuid-s are + * only unique per neighbour (generated via `queue_uuid_gen` + * of `struct Neighbour`). + */ + uint32_t queue_uuid; + /** * Maximum transmission unit supported by this queue. */ @@ -1426,7 +1456,7 @@ struct Neighbour * reassembly. May be NULL if we currently have no fragments from * this @e pid (lazy initialization). */ - struct GNUNET_CONTAINER_MultiShortmap *reassembly_map; + struct GNUNET_CONTAINER_MultiHashMap32 *reassembly_map; /** * Heap with `struct ReassemblyContext` structs for fragments under @@ -1496,6 +1526,26 @@ struct Neighbour */ struct GNUNET_TIME_Absolute earliest_timeout; + /** + * Incremented by one for each queue to generate + * unique queue identifiers. Initially set to a random value. + * + * FIXME: Deal with wrap around (might be triggered by very + * persistent adversary). + */ + uint32_t queue_uuid_gen; + + /** + * Incremented by one for each message sent to this neighbour, to + * uniquely identify that message in replies (note that fragments + * use another additional counter). Initially set to a random value. + * + * It should be safe to assume that by the time this value may wrap + * around, the original message is long "gone" and no longer + * relevant. + */ + uint32_t message_uuid_ctr; + /** * Do we have a confirmed working queue and are thus visible to * CORE? @@ -2421,9 +2471,9 @@ free_reassembly_context (struct ReassemblyContext *rc) GNUNET_assert (rc == GNUNET_CONTAINER_heap_remove_node (rc->hn)); GNUNET_assert (GNUNET_OK == - GNUNET_CONTAINER_multishortmap_remove (n->reassembly_map, - &rc->msg_uuid.uuid, - rc)); + GNUNET_CONTAINER_multihashmap32_remove (n->reassembly_map, + rc->msg_uuid.uuid, + rc)); GNUNET_free (rc); } @@ -2467,9 +2517,7 @@ reassembly_cleanup_task (void *cls) * @return #GNUNET_OK (continue iteration) */ static int -free_reassembly_cb (void *cls, - const struct GNUNET_ShortHashCode *key, - void *value) +free_reassembly_cb (void *cls, uint32_t key, void *value) { struct ReassemblyContext *rc = value; @@ -2499,10 +2547,10 @@ free_neighbour (struct Neighbour *neighbour) GNUNET_SCHEDULER_cancel (neighbour->timeout_task); if (NULL != neighbour->reassembly_map) { - GNUNET_CONTAINER_multishortmap_iterate (neighbour->reassembly_map, - &free_reassembly_cb, - NULL); - GNUNET_CONTAINER_multishortmap_destroy (neighbour->reassembly_map); + GNUNET_CONTAINER_multihashmap32_iterate (neighbour->reassembly_map, + &free_reassembly_cb, + NULL); + GNUNET_CONTAINER_multihashmap32_destroy (neighbour->reassembly_map); neighbour->reassembly_map = NULL; GNUNET_CONTAINER_heap_destroy (neighbour->reassembly_heap); neighbour->reassembly_heap = NULL; @@ -4241,6 +4289,48 @@ send_fragment_ack (struct ReassemblyContext *rc) } +/** + * Closure for #find_by_message_uuid. + */ +struct FindByMessageUuidContext +{ + /** + * UUID to look for. + */ + struct MessageUUIDP message_uuid; + + /** + * Set to the reassembly context if found. + */ + struct ReassemblyContext *rc; +}; + + +/** + * Iterator called to find a reassembly context by the message UUID in the + * multihashmap32. + * + * @param cls a `struct FindByMessageUuidContext` + * @param key a key (unused) + * @param value a `struct ReassemblyContext` + * @return #GNUNET_YES if not found, #GNUNET_NO if found + */ +static int +find_by_message_uuid (void *cls, uint32_t key, void *value) +{ + struct FindByMessageUuidContext *fc = cls; + struct ReassemblyContext *rc = value; + + (void) key; + if (0 == GNUNET_memcmp (&fc->message_uuid, &rc->msg_uuid)) + { + fc->rc = rc; + return GNUNET_NO; + } + return GNUNET_YES; +} + + /** * Communicator gave us a fragment. Process the request. * @@ -4262,6 +4352,7 @@ handle_fragment_box (void *cls, const struct TransportFragmentBoxMessage *fb) char *target; struct GNUNET_TIME_Relative cdelay; int ack_now; + struct FindByMessageUuidContext fc; n = GNUNET_CONTAINER_multipeermap_get (neighbours, &cmc->im.sender); if (NULL == n) @@ -4275,7 +4366,7 @@ handle_fragment_box (void *cls, const struct TransportFragmentBoxMessage *fb) } if (NULL == n->reassembly_map) { - n->reassembly_map = GNUNET_CONTAINER_multishortmap_create (8, GNUNET_YES); + n->reassembly_map = GNUNET_CONTAINER_multihashmap32_create (8); n->reassembly_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); n->reassembly_timeout_task = @@ -4284,9 +4375,13 @@ handle_fragment_box (void *cls, const struct TransportFragmentBoxMessage *fb) n); } msize = ntohs (fb->msg_size); - rc = - GNUNET_CONTAINER_multishortmap_get (n->reassembly_map, &fb->msg_uuid.uuid); - if (NULL == rc) + fc.message_uuid = fb->msg_uuid; + fc.rc = NULL; + GNUNET_CONTAINER_multihashmap32_get_multiple (n->reassembly_map, + fb->msg_uuid.uuid, + &find_by_message_uuid, + &fc); + if (NULL == (rc = fc.rc)) { rc = GNUNET_malloc (sizeof (*rc) + msize + /* reassembly payload buffer */ (msize + 7) / 8 * sizeof (uint8_t) /* bitfield */); @@ -4300,11 +4395,11 @@ handle_fragment_box (void *cls, const struct TransportFragmentBoxMessage *fb) rc, rc->reassembly_timeout.abs_value_us); GNUNET_assert (GNUNET_OK == - GNUNET_CONTAINER_multishortmap_put ( + GNUNET_CONTAINER_multihashmap32_put ( n->reassembly_map, - &rc->msg_uuid.uuid, + rc->msg_uuid.uuid, rc, - GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE)); target = (char *) &rc[1]; rc->bitfield = (uint8_t *) (target + rc->msg_size); rc->msg_missing = rc->msg_size; -- 2.25.1