[GNUnet-SVN] r13850 - gnunet/src/transport

[gnunet]

Author: nevans
Date: 2010-11-30 18:05:17 +0100 (Tue, 30 Nov 2010)
New Revision: 13850

Modified:
   gnunet/src/transport/transport_api.c
Log:
use hashmap instead of linked list of neighbors, fix for double free

Modified: gnunet/src/transport/transport_api.c
===================================================================
--- gnunet/src/transport/transport_api.c        2010-11-30 17:03:18 UTC (rev 
13849)
+++ gnunet/src/transport/transport_api.c        2010-11-30 17:05:17 UTC (rev 
13850)
@@ -60,7 +60,12 @@
  */
 #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 @@
 
 };
 
-
 /**
- * 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 @@
    */
   int is_connected;
 
+  /**
+   * Are we in the middle of disconnecting the peer already?
+   */
+  unsigned int in_disconnect;
+
 };
 
 
@@ -334,7 +364,7 @@
   /**
    * 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 @@
 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,7 +443,88 @@
   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.
  * If none can, schedule a task to call 'schedule_transmission'
@@ -430,88 +538,23 @@
 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;
+  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);
 
-      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 
-
-      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 @@
 
   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,9 +1134,17 @@
 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;
 #if DEBUG_TRANSPORT
@@ -1103,17 +1155,8 @@
   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 @@
 #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 @@
 
 
 /**
+ * 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 @@
 {
   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 @@
       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,18 +1395,60 @@
 #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
  * complete (or fail) asynchronously.
@@ -1382,6 +1483,7 @@
   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 @@
 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_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 @@
   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 @@
       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: