[glib] gmain: Handle case where source id overflows

[Colin Walters <walters src gnome org>]

commit b98a1c8df30f9e24588a48331dacf01e49760549
Author: Colin Walters <walters verbum org>
Date:   Thu Nov 8 09:12:25 2012 -0500

    gmain: Handle case where source id overflows
    
    0 is not a valid source id, but for long-lived programs that rapidly
    create/destroy sources, it's possible for the source id to overflow.
    We should handle this, because the documentation implies we will.
    
    https://bugzilla.gnome.org/show_bug.cgi?id=687098

 glib/glib-private.c   |    3 +-
 glib/glib-private.h   |    5 ++-
 glib/gmain.c          |   76 ++++++++++++++++++++++++++++++++++++++++--
 glib/tests/mainloop.c |   87 +++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 165 insertions(+), 6 deletions(-)
---
diff --git a/glib/glib-private.c b/glib/glib-private.c
index 3506782..e7838a6 100644
--- a/glib/glib-private.c
+++ b/glib/glib-private.c
@@ -40,7 +40,8 @@ glib__private__ (void)
 
     g_get_worker_context,
 
-    g_check_setuid
+    g_check_setuid,
+    g_main_context_new_with_next_id
   };
 
   return &table;
diff --git a/glib/glib-private.h b/glib/glib-private.h
index 87da6f3..23bfb36 100644
--- a/glib/glib-private.h
+++ b/glib/glib-private.h
@@ -27,6 +27,8 @@ G_GNUC_INTERNAL
 GMainContext *          g_get_worker_context            (void);
 G_GNUC_INTERNAL
 gboolean                g_check_setuid                  (void);
+G_GNUC_INTERNAL
+GMainContext *          g_main_context_new_with_next_id (guint next_id);
 
 #define GLIB_PRIVATE_CALL(symbol) (glib__private__()->symbol)
 
@@ -41,9 +43,10 @@ typedef struct {
 
   /* See gmain.c */
   GMainContext *        (* g_get_worker_context)        (void);
-  /* Add other private functions here, initialize them in glib-private.c */
 
   gboolean              (* g_check_setuid)              (void);
+  GMainContext *        (* g_main_context_new_with_next_id) (guint next_id);
+  /* Add other private functions here, initialize them in glib-private.c */
 } GLibPrivateVTable;
 
 GLibPrivateVTable *glib__private__ (void);
diff --git a/glib/gmain.c b/glib/gmain.c
index af1092d..c1776a8 100644
--- a/glib/gmain.c
+++ b/glib/gmain.c
@@ -240,6 +240,7 @@ struct _GMainContext
   gint timeout;			/* Timeout for current iteration */
 
   guint next_id;
+  GHashTable *overflow_used_source_ids; /* set<guint> */
   GList *source_lists;
   gint in_check_or_prepare;
 
@@ -528,6 +529,9 @@ g_main_context_unref (GMainContext *context)
     }
   g_list_free (context->source_lists);
 
+  if (context->overflow_used_source_ids)
+    g_hash_table_destroy (context->overflow_used_source_ids);
+
   g_mutex_clear (&context->mutex);
 
   g_ptr_array_free (context->pending_dispatches, TRUE);
@@ -541,6 +545,18 @@ g_main_context_unref (GMainContext *context)
   g_free (context);
 }
 
+/* Helper function used by mainloop/overflow test.
+ */
+GMainContext *
+g_main_context_new_with_next_id (guint next_id)
+{
+  GMainContext *ret = g_main_context_new ();
+  
+  ret->next_id = next_id;
+  
+  return ret;
+}
+
 /**
  * g_main_context_new:
  * 
@@ -1025,18 +1041,70 @@ source_remove_from_context (GSource      *source,
       context->source_lists = g_list_remove (context->source_lists, source_list);
       g_slice_free (GSourceList, source_list);
     }
+
+  if (context->overflow_used_source_ids)
+    g_hash_table_remove (context->overflow_used_source_ids,
+                         GUINT_TO_POINTER (source->source_id));
+  
+}
+
+static void
+assign_source_id_unlocked (GMainContext   *context,
+                           GSource        *source)
+{
+  guint id;
+
+  /* Are we about to overflow back to 0? 
+   * See https://bugzilla.gnome.org/show_bug.cgi?id=687098
+   */
+  if (G_UNLIKELY (context->next_id == G_MAXUINT &&
+                  context->overflow_used_source_ids == NULL))
+    {
+      GSourceIter iter;
+      GSource *source;
+
+      context->overflow_used_source_ids = g_hash_table_new (NULL, NULL);
+  
+      g_source_iter_init (&iter, context, FALSE);
+      while (g_source_iter_next (&iter, &source))
+        {
+          g_hash_table_add (context->overflow_used_source_ids,
+                            GUINT_TO_POINTER (source->source_id));
+        }
+      id = G_MAXUINT;
+    }
+  else if (context->overflow_used_source_ids == NULL)
+    {
+      id = context->next_id++;
+    }
+  else
+    {
+      /*
+       * If we overran G_MAXUINT, we fall back to randomly probing the
+       * source ids for the current context.  This will be slower the more
+       * sources there are, but we're mainly concerned right now about
+       * correctness and code size.  There's time for a more clever solution
+       * later.
+       */
+      do
+        id = g_random_int ();
+      while (id == 0 ||
+             g_hash_table_contains (context->overflow_used_source_ids,
+                                    GUINT_TO_POINTER (id)));
+      g_hash_table_add (context->overflow_used_source_ids, GUINT_TO_POINTER (id));
+    }
+
+  source->source_id = id;
 }
 
 static guint
 g_source_attach_unlocked (GSource      *source,
 			  GMainContext *context)
 {
-  guint result = 0;
   GSList *tmp_list;
 
   source->context = context;
-  result = source->source_id = context->next_id++;
-
+  assign_source_id_unlocked (context, source);
   source->ref_count++;
   source_add_to_context (source, context);
 
@@ -1054,7 +1122,7 @@ g_source_attach_unlocked (GSource      *source,
       tmp_list = tmp_list->next;
     }
 
-  return result;
+  return source->source_id;
 }
 
 /**
diff --git a/glib/tests/mainloop.c b/glib/tests/mainloop.c
index 3b78c65..02a38e5 100644
--- a/glib/tests/mainloop.c
+++ b/glib/tests/mainloop.c
@@ -21,6 +21,8 @@
  */
 
 #include <glib.h>
+#include "glib-private.h"
+#include <string.h>
 
 static gboolean cb (gpointer data)
 {
@@ -677,6 +679,90 @@ test_source_time (void)
   g_main_context_unref (data.ctx);
 }
 
+typedef struct {
+  guint outstanding_ops;
+  GMainLoop *loop;
+} TestOverflowData;
+
+static gboolean
+on_source_fired_cb (gpointer user_data)
+{
+  TestOverflowData *data = user_data;
+  GSource *current_source;
+  GMainContext *current_context;
+  guint source_id;
+
+  data->outstanding_ops--;
+
+  current_source = g_main_current_source ();
+  current_context = g_source_get_context (current_source);
+  source_id = g_source_get_id (current_source);
+  g_assert (g_main_context_find_source_by_id (current_context, source_id) != NULL);
+  g_source_destroy (current_source);
+  g_assert (g_main_context_find_source_by_id (current_context, source_id) == NULL);
+
+  if (data->outstanding_ops == 0)
+    g_main_loop_quit (data->loop);
+  return FALSE;
+}
+
+static GSource *
+add_idle_source (GMainContext *ctx,
+                 TestOverflowData *data)
+{
+  GSource *source;
+
+  source = g_idle_source_new ();
+  g_source_set_callback (source, on_source_fired_cb, data, NULL);
+  g_source_attach (source, ctx);
+  g_source_unref (source);
+  data->outstanding_ops++;
+
+  return source;
+}
+
+/* https://bugzilla.gnome.org/show_bug.cgi?id=687098 */
+static void
+test_mainloop_overflow (void)
+{
+  GMainContext *ctx;
+  GMainLoop *loop;
+  GSource *source;
+  TestOverflowData data;
+  guint i;
+
+  memset (&data, 0, sizeof (data));
+
+  ctx = GLIB_PRIVATE_CALL (g_main_context_new_with_next_id) (G_MAXUINT-1);
+
+  loop = g_main_loop_new (ctx, TRUE);
+  data.outstanding_ops = 0;
+  data.loop = loop;
+
+  source = add_idle_source (ctx, &data);
+  g_assert_cmpint (source->source_id, ==, G_MAXUINT-1);
+
+  source = add_idle_source (ctx, &data);
+  g_assert_cmpint (source->source_id, ==, G_MAXUINT);
+
+  source = add_idle_source (ctx, &data);
+  g_assert_cmpint (source->source_id, !=, 0);
+
+  /* Now, a lot more sources */
+  for (i = 0; i < 50; i++)
+    {
+      source = add_idle_source (ctx, &data);
+      g_assert_cmpint (source->source_id, !=, 0);
+    }
+
+  g_main_loop_run (loop);
+  g_assert_cmpint (data.outstanding_ops, ==, 0);
+
+  g_main_loop_unref (loop);
+  g_main_context_unref (ctx);
+}
+
+
 int
 main (int argc, char *argv[])
 {
@@ -691,6 +777,7 @@ main (int argc, char *argv[])
   g_test_add_func ("/mainloop/recursive_child_sources", test_recursive_child_sources);
   g_test_add_func ("/mainloop/swapping_child_sources", test_swapping_child_sources);
   g_test_add_func ("/mainloop/source_time", test_source_time);
+  g_test_add_func ("/mainloop/overflow", test_mainloop_overflow);
 
   return g_test_run ();
 }