use hashmap instead of linked list of neighbors, fix for double free

1 files 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,19 +192,39 @@ 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.
    */
   struct GNUNET_TRANSPORT_Handle *h;
@@ -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,
                                                   &quota_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)    
@@ -1153,6 +1197,33 @@ static void demultiplexer (void *cls,
 
 
 /**
+ * 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.
  *
  * @param cls the handle to the 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: