From 7f806de4dcf1c2d71bfad522a2c7f8cf1d82566e Mon Sep 17 00:00:00 2001 From: "Nathan S. Evans" Date: Tue, 30 Nov 2010 17:05:17 +0000 Subject: [PATCH] use hashmap instead of linked list of neighbors, fix for double free --- src/transport/transport_api.c | 377 +++++++++++++++++++++------------- 1 file changed, 230 insertions(+), 147 deletions(-) diff --git a/src/transport/transport_api.c b/src/transport/transport_api.c index 3d35f8d0b..23f8c71a7 100644 --- a/src/transport/transport_api.c +++ b/src/transport/transport_api.c @@ -60,6 +60,11 @@ */ #define STOP_SERVICE_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 5) +/** + * How large to start with for the hashmap of neighbours. + */ +#define STARTING_NEIGHBOURS_SIZE 10 + /** * What stage are we in for transmission processing? @@ -187,18 +192,38 @@ struct ControlMessage }; - /** - * Entry in linked list of all of our current neighbours. + * Context for storing information about attempted next transmission. */ -struct NeighbourList +struct TryTransmitContext { /** - * This is a linked list. + * Main transport handle. */ - struct NeighbourList *next; + struct GNUNET_TRANSPORT_Handle *h; + + /** + * Returned transmission handle. + */ + struct GNUNET_TRANSPORT_TransmitHandle *ret; + /** + * Temporary transmit handle. + */ + struct GNUNET_TRANSPORT_TransmitHandle *th; + + /** + * Time to retry the send task. + */ + struct GNUNET_TIME_Relative retry_time; +}; + +/** + * Entry in hash table of all of our current neighbours. + */ +struct NeighbourList +{ /** * Overall transport handle. */ @@ -235,6 +260,11 @@ struct NeighbourList */ int is_connected; + /** + * Are we in the middle of disconnecting the peer already? + */ + unsigned int in_disconnect; + }; @@ -334,7 +364,7 @@ struct GNUNET_TRANSPORT_Handle /** * Linked list of the current neighbours of this peer. */ - struct NeighbourList *neighbours; + struct GNUNET_CONTAINER_MultiHashMap *neighbours; /** * Peer identity as assumed by this process, or all zeros. @@ -383,13 +413,10 @@ static struct NeighbourList * neighbour_find (struct GNUNET_TRANSPORT_Handle *h, const struct GNUNET_PeerIdentity *peer) { - struct NeighbourList *pos; + if (GNUNET_YES != GNUNET_CONTAINER_multihashmap_contains(h->neighbours, &peer->hashPubKey)) + return NULL; - pos = h->neighbours; - while ((pos != NULL) && - (0 != memcmp (peer, &pos->id, sizeof (struct GNUNET_PeerIdentity)))) - pos = pos->next; - return pos; + return GNUNET_CONTAINER_multihashmap_get(h->neighbours, &peer->hashPubKey); } @@ -416,6 +443,87 @@ quota_transmit_ready (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) schedule_transmission (h); } +/** + * Iterator over hash map entries, attempt to schedule + * a transmission to entries in the neighbour hashmap. + * + * @param cls closure a TryTransmitContext + * @param key current key code + * @param value value in the hash map, the neighbour entry to consider + * @return GNUNET_YES if we should continue to + * iterate, + * GNUNET_NO if not. + */ +static int +try_schedule_transmission (void *cls, + const GNUNET_HashCode * key, + void *value) +{ + struct NeighbourList *n = value; + struct TryTransmitContext *try_transmit_ctx = cls; + struct GNUNET_TIME_Relative duration; + GNUNET_CONNECTION_TransmitReadyNotify notify; + + if (n->transmit_stage != TS_QUEUED) + return GNUNET_YES; /* not eligible, keep iterating */ + if (n->is_connected != GNUNET_YES) + return GNUNET_YES; /* keep iterating */ + + try_transmit_ctx->th = &n->transmit_handle; + GNUNET_break (n == try_transmit_ctx->th->neighbour); + /* check outgoing quota */ + duration = GNUNET_BANDWIDTH_tracker_get_delay (&n->out_tracker, + try_transmit_ctx->th->notify_size - sizeof (struct OutboundMessage)); + struct GNUNET_TIME_Absolute duration_abs = GNUNET_TIME_relative_to_absolute (duration); + if (try_transmit_ctx->th->timeout.abs_value < duration_abs.abs_value) + { + /* signal timeout! */ +#if DEBUG_TRANSPORT + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Would need %llu ms before bandwidth is available for delivery to `%4s', that is too long. Signaling timeout.\n", + duration.rel_value, + GNUNET_i2s (&n->id)); +#endif + if (try_transmit_ctx->th->notify_delay_task != GNUNET_SCHEDULER_NO_TASK) + { + GNUNET_SCHEDULER_cancel (try_transmit_ctx->th->notify_delay_task); + try_transmit_ctx->th->notify_delay_task = GNUNET_SCHEDULER_NO_TASK; + } + n->transmit_stage = TS_NEW; + if (NULL != (notify = try_transmit_ctx->th->notify)) + { + try_transmit_ctx->th->notify = NULL; + GNUNET_assert (0 == notify (try_transmit_ctx->th->notify_cls, 0, NULL)); + } + return GNUNET_YES; /* keep iterating */ + } + if (duration.rel_value > 0) + { +#if DEBUG_TRANSPORT + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Need more bandwidth (%u b/s allowed, %u b needed), delaying delivery to `%4s' by %llu ms\n", + (unsigned int) n->out_tracker.available_bytes_per_s__, + (unsigned int) try_transmit_ctx->th->notify_size - sizeof (struct OutboundMessage), + GNUNET_i2s (&n->id), + duration.rel_value); +#endif + try_transmit_ctx->retry_time = GNUNET_TIME_relative_min (try_transmit_ctx->retry_time, + duration); + return GNUNET_YES; /* keep iterating */ + } +#if DEBUG_TRANSPORT + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Have %u bytes of bandwidth available for transmission to `%4s' right now\n", + try_transmit_ctx->th->notify_size - sizeof (struct OutboundMessage), + GNUNET_i2s (&n->id)); +#endif + + if ( (try_transmit_ctx->ret == NULL) || + (try_transmit_ctx->ret->priority < try_transmit_ctx->th->priority) ) + try_transmit_ctx->ret = try_transmit_ctx->th; + + return GNUNET_YES; +} /** * Figure out which transmission to a peer can be done right now. @@ -430,88 +538,23 @@ quota_transmit_ready (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) static struct GNUNET_TRANSPORT_TransmitHandle * schedule_peer_transmission (struct GNUNET_TRANSPORT_Handle *h) { - struct GNUNET_TRANSPORT_TransmitHandle *ret; - struct GNUNET_TRANSPORT_TransmitHandle *th; - struct NeighbourList *n; - struct NeighbourList *next; - struct GNUNET_TIME_Relative retry_time; - struct GNUNET_TIME_Relative duration; - GNUNET_CONNECTION_TransmitReadyNotify notify; + + struct TryTransmitContext try_transmit_ctx; if (h->quota_task != GNUNET_SCHEDULER_NO_TASK) { GNUNET_SCHEDULER_cancel (h->quota_task); h->quota_task = GNUNET_SCHEDULER_NO_TASK; } - retry_time = GNUNET_TIME_UNIT_FOREVER_REL; - ret = NULL; - next = h->neighbours; - while (NULL != (n = next)) - { - next = n->next; - if (n->transmit_stage != TS_QUEUED) - continue; /* not eligible */ - if (n->is_connected != GNUNET_YES) - continue; - - th = &n->transmit_handle; - GNUNET_break (n == th->neighbour); - /* check outgoing quota */ - duration = GNUNET_BANDWIDTH_tracker_get_delay (&n->out_tracker, - th->notify_size - sizeof (struct OutboundMessage)); - struct GNUNET_TIME_Absolute duration_abs = GNUNET_TIME_relative_to_absolute (duration); - if (th->timeout.abs_value < duration_abs.abs_value) - { - /* signal timeout! */ -#if DEBUG_TRANSPORT - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Would need %llu ms before bandwidth is available for delivery to `%4s', that is too long. Signaling timeout.\n", - duration.rel_value, - GNUNET_i2s (&n->id)); -#endif - if (th->notify_delay_task != GNUNET_SCHEDULER_NO_TASK) - { - GNUNET_SCHEDULER_cancel (th->notify_delay_task); - th->notify_delay_task = GNUNET_SCHEDULER_NO_TASK; - } - n->transmit_stage = TS_NEW; - if (NULL != (notify = th->notify)) - { - th->notify = NULL; - GNUNET_assert (0 == notify (th->notify_cls, 0, NULL)); - } - continue; - } - if (duration.rel_value > 0) - { -#if DEBUG_TRANSPORT - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Need more bandwidth (%u b/s allowed, %u b needed), delaying delivery to `%4s' by %llu ms\n", - (unsigned int) n->out_tracker.available_bytes_per_s__, - (unsigned int) th->notify_size - sizeof (struct OutboundMessage), - GNUNET_i2s (&n->id), - duration.rel_value); -#endif - retry_time = GNUNET_TIME_relative_min (retry_time, - duration); - continue; - } -#if DEBUG_TRANSPORT - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Have %u bytes of bandwidth available for transmission to `%4s' right now\n", - th->notify_size - sizeof (struct OutboundMessage), - GNUNET_i2s (&n->id)); -#endif + memset(&try_transmit_ctx, 0, sizeof(struct TryTransmitContext)); + try_transmit_ctx.retry_time = GNUNET_TIME_UNIT_FOREVER_REL; + GNUNET_CONTAINER_multihashmap_iterate(h->neighbours, &try_schedule_transmission, &try_transmit_ctx); - if ( (ret == NULL) || - (ret->priority < th->priority) ) - ret = th; - } - if (ret == NULL) - h->quota_task = GNUNET_SCHEDULER_add_delayed (retry_time, + if (try_transmit_ctx.ret == NULL) + h->quota_task = GNUNET_SCHEDULER_add_delayed (try_transmit_ctx.retry_time, "a_transmit_ready, h); - return ret; + return try_transmit_ctx.ret; } @@ -809,9 +852,10 @@ send_set_quota (void *cls, size_t size, void *buf) if (buf == NULL) { - GNUNET_SCHEDULER_add_continuation (sqc->cont, - sqc->cont_cls, - GNUNET_SCHEDULER_REASON_TIMEOUT); + if (sqc->cont != NULL) + GNUNET_SCHEDULER_add_continuation (sqc->cont, + sqc->cont_cls, + GNUNET_SCHEDULER_REASON_TIMEOUT); GNUNET_free (sqc); return 0; } @@ -1090,8 +1134,16 @@ static void neighbour_free (struct NeighbourList *n) { struct GNUNET_TRANSPORT_Handle *h; - struct NeighbourList *prev; - struct NeighbourList *pos; + + /* Added so task gets canceled when a disconnect is received! */ + /* Method 1 + if (n->transmit_handle.notify_delay_task != GNUNET_SCHEDULER_NO_TASK) + { + GNUNET_SCHEDULER_cancel(n->transmit_handle.notify_delay_task); + n->transmit_handle.notify_delay_task = GNUNET_SCHEDULER_NO_TASK; + n->transmit_handle.notify = NULL; + } + */ GNUNET_assert (n->transmit_handle.notify == NULL); h = n->h; @@ -1103,17 +1155,8 @@ neighbour_free (struct NeighbourList *n) GNUNET_break (n->is_connected == GNUNET_NO); GNUNET_break (n->transmit_stage == TS_NEW); - prev = NULL; - pos = h->neighbours; - while (pos != n) - { - prev = pos; - pos = pos->next; - } - if (prev == NULL) - h->neighbours = n->next; - else - prev->next = n->next; + GNUNET_assert(GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove(h->neighbours, &n->id.hashPubKey, n)); + GNUNET_free (n); } @@ -1134,6 +1177,7 @@ neighbour_disconnect (struct NeighbourList *n) #endif GNUNET_break (n->is_connected == GNUNET_YES); n->is_connected = GNUNET_NO; + n->in_disconnect = GNUNET_YES; if (h->nd_cb != NULL) h->nd_cb (h->cls, &n->id); if (n->transmit_stage == TS_NEW) @@ -1152,6 +1196,33 @@ static void demultiplexer (void *cls, const struct GNUNET_MessageHeader *msg); +/** + * Iterator over hash map entries, for getting rid of a neighbor + * upon a reconnect call. + * + * @param cls closure (NULL) + * @param key current key code + * @param value value in the hash map, the neighbour entry to forget + * @return GNUNET_YES if we should continue to + * iterate, + * GNUNET_NO if not. + */ +static int +forget_neighbours (void *cls, + const GNUNET_HashCode * key, + void *value) +{ + struct NeighbourList *n = value; +#if DEBUG_TRANSPORT_DISCONNECT + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Disconnecting due to reconnect being called\n"); +#endif + if (n->is_connected) + neighbour_disconnect (n); + + return GNUNET_YES; +} + /** * Try again to connect to transport service. * @@ -1164,8 +1235,6 @@ reconnect (void *cls, { struct GNUNET_TRANSPORT_Handle *h = cls; struct ControlMessage *pos; - struct NeighbourList *n; - struct NeighbourList *next; h->reconnect_task = GNUNET_SCHEDULER_NO_TASK; if ( (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN) != 0) @@ -1174,18 +1243,8 @@ reconnect (void *cls, return; } /* Forget about all neighbours that we used to be connected to */ - n = h->neighbours; - while (NULL != n) - { -#if DEBUG_TRANSPORT_DISCONNECT - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Disconnecting due to reconnect being called\n"); -#endif - next = n->next; - if (n->is_connected) - neighbour_disconnect (n); - n = next; - } + GNUNET_CONTAINER_multihashmap_iterate(h->neighbours, &forget_neighbours, NULL); + #if DEBUG_TRANSPORT GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Connecting to transport service.\n"); @@ -1336,17 +1395,59 @@ neighbour_add (struct GNUNET_TRANSPORT_Handle *h, #endif n = GNUNET_malloc (sizeof (struct NeighbourList)); n->id = *pid; + n->h = h; GNUNET_BANDWIDTH_tracker_init (&n->out_tracker, GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT, MAX_BANDWIDTH_CARRY_S); - n->next = h->neighbours; - n->h = h; - h->neighbours = n; - + GNUNET_CONTAINER_multihashmap_put (h->neighbours, + &pid->hashPubKey, + n, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); return n; } +/** + * Iterator over hash map entries, for deleting state of a neighbor. + * + * @param cls closure (NULL) + * @param key current key code + * @param value value in the hash map, the neighbour entry to delete + * @return GNUNET_YES if we should continue to + * iterate, + * GNUNET_NO if not. + */ +static int +delete_neighbours (void *cls, + const GNUNET_HashCode * key, + void *value) +{ + struct NeighbourList *n = value; + struct GNUNET_TRANSPORT_TransmitHandle *th; + + switch (n->transmit_stage) + { + case TS_NEW: + case TS_TRANSMITTED: + /* nothing to do */ + break; + case TS_QUEUED: + case TS_TRANSMITTED_QUEUED: + th = &n->transmit_handle; + if (th->notify_delay_task != GNUNET_SCHEDULER_NO_TASK) + { + GNUNET_SCHEDULER_cancel (th->notify_delay_task); + th->notify_delay_task = GNUNET_SCHEDULER_NO_TASK; + } + GNUNET_assert (0 == th->notify (th->notify_cls, 0, NULL)); + break; + default: + GNUNET_break (0); + } + GNUNET_free (n); + return GNUNET_YES; +} + /** * Connect to the transport service. Note that the connection may @@ -1382,6 +1483,7 @@ GNUNET_TRANSPORT_connect (const struct GNUNET_CONFIGURATION_Handle *cfg, ret->nc_cb = nc; ret->nd_cb = nd; ret->reconnect_delay = GNUNET_TIME_UNIT_ZERO; + ret->neighbours = GNUNET_CONTAINER_multihashmap_create(STARTING_NEIGHBOURS_SIZE); schedule_reconnect (ret); return ret; } @@ -1393,8 +1495,6 @@ GNUNET_TRANSPORT_connect (const struct GNUNET_CONFIGURATION_Handle *cfg, void GNUNET_TRANSPORT_disconnect (struct GNUNET_TRANSPORT_Handle *handle) { - struct GNUNET_TRANSPORT_TransmitHandle *th; - struct NeighbourList *n; struct HelloWaitList *hwl; struct GNUNET_CLIENT_Connection *client; struct ControlMessage *cm; @@ -1403,30 +1503,13 @@ GNUNET_TRANSPORT_disconnect (struct GNUNET_TRANSPORT_Handle *handle) GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Transport disconnect called!\n"); #endif handle->in_disconnect = GNUNET_YES; - while (NULL != (n = handle->neighbours)) - { - handle->neighbours = n->next; - switch (n->transmit_stage) - { - case TS_NEW: - case TS_TRANSMITTED: - /* nothing to do */ - break; - case TS_QUEUED: - case TS_TRANSMITTED_QUEUED: - th = &n->transmit_handle; - if (th->notify_delay_task != GNUNET_SCHEDULER_NO_TASK) - { - GNUNET_SCHEDULER_cancel (th->notify_delay_task); - th->notify_delay_task = GNUNET_SCHEDULER_NO_TASK; - } - GNUNET_assert (0 == th->notify (th->notify_cls, 0, NULL)); - break; - default: - GNUNET_break (0); - } - GNUNET_free (n); - } + + GNUNET_assert(GNUNET_SYSERR != + GNUNET_CONTAINER_multihashmap_iterate(handle->neighbours, + &delete_neighbours, + handle)); + GNUNET_CONTAINER_multihashmap_destroy(handle->neighbours); + while (NULL != (hwl = handle->hwl_head)) { handle->hwl_head = hwl->next; @@ -1902,7 +1985,7 @@ GNUNET_TRANSPORT_notify_transmit_ready_cancel (struct n = th->neighbour; #if DEBUG_TRANSPORT GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, - "Transmission request of %u bytes to `%4s' was cancelled.\n", + "Transmission request of %u bytes to `%4s' was canceled.\n", th->notify_size - sizeof (struct OutboundMessage), GNUNET_i2s (&n->id)); #endif @@ -1918,7 +2001,7 @@ GNUNET_TRANSPORT_notify_transmit_ready_cancel (struct break; case TS_QUEUED: n->transmit_stage = TS_NEW; - if (n->is_connected == GNUNET_NO) + if (n->in_disconnect == GNUNET_NO) neighbour_free (n); break; case TS_TRANSMITTED: -- 2.25.1