ignoring the larger issue, you can work around this in your code by using the GSource-based APIs instead of the guint-based ones.

I'm not sure I understood what you meant by: "using the GSource-based APIs".

Using g_timeout_source_new() doesn't solve the problem as I still have to call g_source_attach() after, which is affected by the bug.

Please correct me if I missed the function were talking about.

You will at some point end up with a GSource whose id is 0, but you don't ever have to look at that id, so you don't care.

I'm sorry, I phrased my first question wrongly.

I need this ID as I'm using g_main_context_find_source_by_id() which will fail to process an ID=0.

This could be changed by removing checks like this one:

gmain.c
1889:  g_return_val_if_fail (source_id > 0, NULL);

which don't seem to be useful (I may be wrong here, I don't know the glib well).

I could use g_main_context_find_source_by_user_data() instead and I'll probably do that.

I agree with you, this bug seems to be harmless. Nevertheless the documentation should be updated to reflects those "limits" and warn about excessive use of g_timeout_add functions. At least the documentation should not imply that IDs are never == 0.

I cannot find a reason to not start IDs at 0.

Thanks

(In reply to comment #4)
> I'm sorry, I phrased my first question wrongly.
> 
> I need this ID as I'm using g_main_context_find_source_by_id() which will fail
> to process an ID=0.

if you keep a pointer to the GSource you don't need to use the id-based API at all.

> I cannot find a reason to not start IDs at 0.

because 0 is an error value, and existing code would break if we changed it.

> because 0 is an error value, and existing code would break if we changed it.

Ok, so the current code has to be changed to never return 0 or maybe you should deprecate the use of those IDs to prevent futur code from relying on it.

This is actually a serious problem because the PyGObject bindings rely upon the returned number, and it creates a serious bug when the number wraps around.
Refer to bug #684526.

(In reply to comment #6)
> > because 0 is an error value, and existing code would break if we changed it.
> 
> Ok, so the current code has to be changed to never return 0 or maybe you should
> deprecate the use of those IDs to prevent futur code from relying on it.

It'd be a two-line patch to just ensure we never return 0.  But if people are actually hitting this overflow case, it seems quite possible to me that you could still have a source whose id is 1 (e.g. added early on process startup and never removed).  If you then tried to remove the source with id 1, you'd hit that first source.

One thing - both pygobject and gjs have the ability to return larger integers - in gjs' case, doubles cover 2^52, a substantially larger range.  

Another approach here is to detect the case when we overflow, and create a hash table for the currently active source ids, and ensure we don't return those.

The importance of this bug needs to be elevated to high/critical because it
both contains flawed logic (when the returned number wraps, there will be two
objects with the same number) and it causes data loss (when the number wraps,
it is possible that there will be more than one object with the same number,
and when glib.source_remove() is called in such a case, the result is undefined
and will cause an application to malfunction in unpredictable ways).
Also the documentation for g_source_attach() claims that it will return a value
greater than 0 which is clearly not true if the number wraps. (Some code looks
for 0 as an error, so this effectively becomes a counter to an error.)

It seems like a proper fix (or work-around) would be to wrap around from max to
1, then check if the number is taken, if so, increment and check again until an
unused number is selected. This is likely to be a better fix than simply
picking the lowest unused number because there may be sloppy coding at higher
levels that may confuse things if the same number is returned in a short period
of time.

(In reply to comment #8)
>
> 
> Another approach here is to detect the case when we overflow, and create a hash
> table for the currently active source ids, and ensure we don't return those.

I'm against complications like this which have a cost, just to fix up the convenience api. We should just document that if you plan to create > 2^32 sources, don't use id, but use g_source_attach()/g_source_remove().

A possible solution would be to use the GSource pointer turned into a guint as an ID. Adding a timeout with g_timeout_add() seems to always create a new GSource *, easily giving us a unique and free to use ID.

This may not work with architecture/platforms on which sizeof(pointer) > sizeof(guint), but then one could hope that <GSource pointer> * sizeof(guint)/sizeof(pointer) would give us a unique ID.

This should not impact performance. As far as I understand, the fact that those ids are not consecutive and incrementing should not impact functions such as g_main_context_find_source_by_id().

Code relying on the fact that those IDs were always increasing would be impacted, but this behaviour is not written in the documentation and thus should not be expected.

(In reply to comment #11)
> A possible solution would be to use the GSource pointer turned into a guint as
> an ID. Adding a timeout with g_timeout_add() seems to always create a new
> GSource *, easily giving us a unique and free to use ID.

On some platforms (ARM for example) I have seen where creating a new GSource, then freeing it then new again will return the same address.  While that should be ok, it is possible that returning the same number again may break sloppy code that may attempt to remove the same object more than once.

> <GSource pointer> * sizeof(guint)/sizeof(pointer) would give us a unique ID.

This does not rule out returning zero in the case of sizeof(pointer) > sizeof(guint), nor does it prevent two objects from returning the same id.

(In reply to comment #10)

> I'm against complications like this which have a cost, just to fix up the
> convenience api. We should just document that if you plan to create > 2^32
> sources, don't use id, but use g_source_attach()/g_source_remove().

Convenience API or not, it's broken, and the PyGObject bindings rely upon it working. Changing the documentation will not help the users of PyGObject, from that end, there is not an alternative. The authors of PyGObject would have to change their code to work around this. The question is how many others would have to do the same. It seems more direct to fix what is known to be broken than ask everyone else to work around it.

(In reply to comment #12)
> On some platforms (ARM for example) I have seen where creating a new GSource,
> then freeing it then new again will return the same address.  While that should
> be ok, it is possible that returning the same number again may break sloppy
> code that may attempt to remove the same object more than once.

This is indeed a problem. But this is a bug in the application code anyway, not in the glib.

> This does not rule out returning zero in the case of sizeof(pointer) >
> sizeof(guint)

<GSource pointer> * sizeof(guint)/sizeof(pointer) = 0 would mean that <GSource pointer> is pointing to an address between 0 and <sizeof(pointer)> at worst. It seems not possible, on a Linux system at least, to have such address available for dynamic memory allocation (it's either program code or kernel reserved memory).

> nor does it prevent two objects from returning the same id.

GSource structures consists of at least 8 pointers, which would make it impossible for the kernel to allocate memory for a struct GSource at an address in the same "sizeof(pointer)" slice of memory of an other GSource struct. Thus, two objects will never have the same id (at least on Linux).

(In reply to comment #10)
> (In reply to comment #8)
> >
> > 
> > Another approach here is to detect the case when we overflow, and create a hash
> > table for the currently active source ids, and ensure we don't return those.
> 
> I'm against complications like this which have a cost, just to fix up the
> convenience api. We should just document that if you plan to create > 2^32
> sources, don't use id, but use g_source_attach()/g_source_remove().

The issue I have with that is that documenting it *now* doesn't help all the apps that have been written.  And a lot of the APIs like g_source_attach() *explicitly* say "greater than 0".  It's quite reasonable for them to have expected that this would work.

The question though is - how hard/invasive is a fix?

Created attachment 228472 [details] [review]
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.

The patch above can be tested by manually changing the initial context->next_id = 1 to something higher, like G_MAXUINT - 2.

Note to future API designers: Use gpointer for opaque keys, not guint.

(In reply to comment #10)
> I'm against complications like this which have a cost, just to fix up the
> convenience api. We should just document that if you plan to create > 2^32
> sources, don't use id, but use g_source_attach()/g_source_remove().

There's still the possibility that in the case of an id getting reused, the other person could accidentally remove your source rather than the other way around.

(In reply to comment #12)
> On some platforms (ARM for example) I have seen where creating a new GSource,
> then freeing it then new again will return the same address.

This isn't a platform thing, it's caused by glib's slice allocator.

(In reply to comment #13)
> Convenience API or not, it's broken, and the PyGObject bindings rely upon it
> working.

This should probably be considered a bug; the guint API is there to save C users from having to memory-manage their GSources. There is no reason to not just use the GSource* API from garbage-collected language bindings. (But this isn't just pygobject; gjs uses the guint APIs too. Probably because GSource didn't used to be boxed.) And as Colin notes in comment 8, both bindings can just return pointer-sized ints rather than int-sized ints, so they could fix this transparently.

(In reply to comment #15)
> The question though is - how hard/invasive is a fix?

I think the problem is not so much hard/invasive as "unpleasantly O(n)"...

Comment on attachment 228472 [details] [review]
gmain: Handle case where source id overflows

Ah, sure, I guess we only need to take the O(n) hit once...

>+  /* Are we going to overflow? */
>+  if (G_UNLIKELY (context->next_id == G_MAXUINT &&
>+                  context->overflow_used_source_ids == NULL))

you could make that "Did we overflow" / "next_id == 0" too

>+          g_hash_table_insert (context->overflow_used_source_ids,

You could use g_hash_table_add() since you're using it as a set. (Here and below.)

> The patch above can be tested by manually changing the initial context->next_id
> = 1 to something higher, like G_MAXUINT - 2.

I think we should definitely have a test for it in tests/. You could import the definition of struct GMainContext into the test, and then add a few sources and g_assert that the field that you think is next_id actually changes appropriately (to make sure the test breaks if someone rearranges GMainContext without updating the test), and then set it to G_MAXUINT - 2, add some more sources, etc.

Wouldn't something like that work as well ? The only issue seems to be the
address re-use which could trigger bugs in buggy code.

glib/gmain.c
@@ -1035,7 +1035,7 @@ g_source_attach_unlocked (GSource *source...)
   GSList *tmp_list;

   source->context = context;
-  result = source->source_id = ((guintptr) source / sizeof(source)) *
sizeof(result);
+  result = source->source_id = context->next_id++;

   source->ref_count++;
   source_add_to_context (source, context);

(In reply to comment #21)
> Wouldn't something like that work as well ?

Your definition of "work" must mean "will cause incorrect behavior less often".  I wouldn't put my name on code like that.

> The only issue seems to be the
> address re-use which could trigger bugs in buggy code.

No, because it's entirely possible that whatever integer you calculate happens to be in use by an existing source id.

Also, it'd be awesome if one of you guys (Neil, Timothée) tested the patch.

(In reply to comment #22)
> (In reply to comment #21)
> > Wouldn't something like that work as well ?
> 
> Your definition of "work" must mean "will cause incorrect behavior less often".
>  I wouldn't put my name on code like that.

> Note to future API designers: Use gpointer for opaque keys, not guint.

This will cause incorrect behavior only with code already behaving incorrectly. Using gpointers for this or future API won't solve this issue.

> > The only issue seems to be the
> > address re-use which could trigger bugs in buggy code.
> 
> No, because it's entirely possible that whatever integer you calculate happens
> to be in use by an existing source id.

Then please tell me what's wrong in my reasoning in comment 14.

> Also, it'd be awesome if one of you guys (Neil, Timothée) tested the patch.

I'll try it with the test app I used to reproduce the bug.

Ok, here is a compromise between changing any of the structures and performance:

 {
   guint result = 0;
   GSList *tmp_list;
+  GSource *tmp_source;
 
   source->context = context;
-  result = source->source_id = context->next_id++;
+  do 
+    {
+      result = source->source_id = context->next_id++;
+      for (tmp_source = context->source_list; tmp_source && result; tmp_source = tmp_source->next)
+        if (tmp_source->source_id == result)
+          {
+            result = 0;
+            break;
+          }
+    } while (! result);
 
   source->ref_count++;
   g_source_list_add (source, context);

This actually fixes the id problem in a way that is highly unlikely to bring out bugs in sloppy code that tries to remove the same id more than once in a short period of time, however on the flip side, it is not very efficient because it has to walk the list and retry if there is an id conflict.

(In reply to comment #24)
>
> Then please tell me what's wrong in my reasoning in comment 14.

Admittedly, it would likely work in practice everywhere we care about.  It will definitely work on 32 bit.  But conceptually, the problem is that on 64 bit machines, we're making assumptions about the address space.  Now, at present, x86_64 for example is defined to only have 48 bits of address space, because 256 TB is a lot of RAM:
http://en.wikipedia.org/wiki/X86-64

Even with 48 bits though, you are making the assumpton that the higher order bits are the same.  Probably again at the moment, unlikely.  But it's not the kind of thing I think is a good idea to bake in, given that for security reasons, unpredictabe addresses are good, and also that x86_64 allows for the full 64 bit address space to be used in future processors.

(In reply to comment #25)
> Even with 48 bits though, you are making the assumption that the higher order
> bits are the same. Probably again at the moment, unlikely.

Sorry, I don't understand what's the problem here. I'm using this address only to generate an id which will never be converted back to an address. I does not really matter what's the address, we just need to make sure it's unique which is kind of expected since it is allocated by malloc at some point.

> But it's not the
> kind of thing I think is a good idea to bake in, given that for security
> reasons, unpredictable addresses are good, and also that x86_64 allows for the
> full 64 bit address space to be used in future processors.

Unpredictable addresses and full 64bit addresses does not impact the id generation process, and the more random the address/generated id is, the best.

The code that tries do find a GSource by it's id (gmain.c:1882 g_main_context_find_source_by_id) does not make any assumption about id ordering so it seems to be safe to use such random ids.

I understand the fact that you don't want to rely on any particular architecture memory layout. But is there an other (virtual) memory layout used and with a supported version of the glib ?

Can we stop all the distracting talk about address spaces and security ? 
If you create enough sources that wraparound is a concern, simply don't use the id-based convenience api, but use g_source_attach/g_source_remove directly.

That's what I did (thanks to comment #5). I just though the documentation (at least) should be updated to warn developers about this issue. I only offered solutions to try to fix this issue for more people without having them to change their code. I'll try to come with an example patch for the documentation.

(In reply to comment #19)
> (In reply to comment #13)
> > Convenience API or not, it's broken, and the PyGObject bindings rely upon it
> > working.
> 
> This should probably be considered a bug; the guint API is there to save C
> users from having to memory-manage their GSources. There is no reason to not
> just use the GSource* API from garbage-collected language bindings.

filed bug 687987 (gjs) and bug 687988 (pygobject). java-gnome apparently doesn't export the guint- or GSource*-based APIs.

(In reply to comment #30)
> filed bug 687987 (gjs) and bug 687988 (pygobject). java-gnome apparently
> doesn't export the guint- or GSource*-based APIs.

Good move, it is clear that these bindings are using the wrong API. However, this does not change the fact that the convenience API is broken and needs to be fixed, and that there are two clear options to fix it:

1. We use the address of the object as described in 21.

2. We use a number that wraps around and skips still active numbers as described in 24.

I personally vote for 2. The logic is as follows:
It is the closest behavior to what authors are expecting from the existing API, and highly unlikely to break any existing code. Many OS kernels use this approach when assigning PID numbers; it is expected and known. It is easy for a human to look at debugging information and get an idea for the order that events occurred. There is zero chance of it having a collision or returning a 0, however it will deadlock if the total amount of objects in use equal the storage size of gunit-1, but I think that even a large computer would be memory exhausted or thrashing long before then. It is not efficient, but it is a convenience API, if you want to have efficiency, you can use the other API, leave it up to the author to choose. The lack of efficiency only shows when a large number of objects are in use. No data structures need to be changed, which would not be the case if we were to keep track of the used numbers somewhere.
That's my two cents worth... Unless someone can shoot this down, I think we should use 2.

(In reply to comment #20)
> (From update of attachment 228472 [details] [review])
> Ah, sure, I guess we only need to take the O(n) hit once...
> 
> >+  /* Are we going to overflow? */
> >+  if (G_UNLIKELY (context->next_id == G_MAXUINT &&
> >+                  context->overflow_used_source_ids == NULL))
> 
> you could make that "Did we overflow" / "next_id == 0" too

I wrote it that way the first time, but it duplicated the code too much; this way is fairly clear I think that the overflow is a one-time special case.

> >+          g_hash_table_insert (context->overflow_used_source_ids,
> 
> You could use g_hash_table_add() since you're using it as a set. (Here and
> below.)

Done.

> > The patch above can be tested by manually changing the initial context->next_id
> > = 1 to something higher, like G_MAXUINT - 2.
> 
> I think we should definitely have a test for it in tests/. You could import the
> definition of struct GMainContext into the test, 

Eeek.  Let's brainstorm a bit about less ugly ways to test it.  What about a GLIB_PRIVATE () api like g_main_context_new_with_next_id () ?

Created attachment 228656 [details] [review]
gmain: Handle case where source id overflows

Adds a test case using GLIB_PRIVATE api.  Also, fixes a bug I noticed
in code review where in theory g_random_int() could return 0...

Created attachment 228657 [details] [review]
gmain: Handle case where source id overflows

Forgot to git add the test

Comment on attachment 228657 [details] [review]
gmain: Handle case where source id overflows

>   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 */

Maybe add a comment noting that this is only expected to be used by test programs? (If we end up with more than one or two such functions, it might be worth splitting them out into a separate vtable...)

>-g_main_context_new (void)
>+g_main_context_new_with_next_id (guint next_id)

given how rarely new_with_next_id will be used, I think it would make more sense to leave the real code in g_main_context_new(), and then have

GMainContext *
g_main_context_new_with_next_id (guint next_id)
{
  GMainContext *context = g_main_context_new ();

  context->next_id = next_id;
  return context;
}

(saves an extra function call in the normal case, and leaves the code in the place where you'd expect to find it when searching through the file.)

>+      while (id == 0 ||
>+             g_hash_table_contains (context->overflow_used_source_ids,
>+                                    GUINT_TO_POINTER (id)));

good catch on the == 0.

it occurs to me that this will loop forever if you add a new source to a context that already has G_MAXUINT sources... which would be really pathological, and I guess there's nothing else we could do besides abort anyway, so, probably ok.

>+TEST_PROGS      += mainloop-overflow
>+mainloop_overflow_LDADD   = $(progs_ldadd)

no need for a new program, you can just add a new test to mainloop.c.

>+static gboolean
>+on_source_fired_cb (gpointer user_data)
>+{
>+  TestOverflowData *data = user_data;
>+  data->outstanding_ops--;
>+  if (data->outstanding_ops == 0)
>+    g_main_loop_quit (data->loop);
>+  return FALSE;
>+}

you can also verify that source IDs aren't getting reused by adding:

  source_id = g_source_get_id (g_main_current_source ());
  g_assert (g_main_context_find_source_by_id (NULL, source_id) != NULL);
  g_source_remove (source_id);
  g_assert (g_main_context_find_source_by_id (NULL, source_id) == NULL);

Created attachment 228799 [details] [review]
gmain: Handle case where source id overflows

Updated for comments

Comment on attachment 228799 [details] [review]
gmain: Handle case where source id overflows

yay

Attachment 228799 [details] pushed as b98a1c8 - gmain: Handle case where source id overflows