Re: GLib source id wrap around

[Owen Taylor <otaylor redhat com>]

On Thu, 2003-10-09 at 20:51, Max Krasnyansky wrote:
> Folks,
> 
> Sorry of this has been discussed before.
> It seems to me that source id wrap around is not handled properly.
> After looking at the source of g_source attach() it was pretty clear 
> to me that return 0 means failure. However source id is allocated
> by simply incrementing context->next_id, which is unsigned int and is 
> initialized to 1. So eventually it will wrap around and become zero.
> Am I missing something here ?

Yes, if you wrap source ID's around things will go bad. It's only
a problem for the legacy API, since the API these days encourages
using GSource * rather than IDs, but there are quite a few things
still around using IDs.

> Here is the relevant portion of g_source_attach()
> /**
>  * ...
>  * Return value: the ID for the source within the #GMainContext
>  **/
> guint
> g_source_attach (GSource      *source,
>                  GMainContext *context)
> {
>   guint result = 0;
>   GSList *tmp_list;
> 
>   g_return_val_if_fail (source->context == NULL, 0);
>   g_return_val_if_fail (!SOURCE_DESTROYED (source), 0);
>   
>   if (!context)
>     context = g_main_context_default ();
> 
>   LOCK_CONTEXT (context);
> 
>   source->context = context;
>   result = source->source_id = context->next_id++;
> 
>   ...
> 
>   return result;
> }
> (latest CVS. HEAD branch.)
> 
> I'd say we need to add something like following to that function.
>         /* Handle wrap around. id 0 is invalid */
>         if (!context->next_id)
>                 context->next_id = 1;

That won't work, since it doesn't guarantee uniqueness. Getting around
that without introducing significant overhead isn't obvious to me..
storing all used IDs in a sorted data structure is possible, but
expensive.

Another possibility is to keep track of the next range of unused
IDs ... it gives you excellent performance until you wrap around
the first time, and after that, still should perform pretty
well on average as long as the total ID space is sparsely 
occupied.

 if (context->next_id == context->next_used_id)
   {
     /* Recalculate context->next_id and next_used_id;
      * a bit expensive, but can be done O(n_sources)
      */
   } 
 else
   {
     source_id = context->next_id++;
   }

> Also it looks like some glib functions don't bother checking for errors ;-).
> For example g_source_new() does
>           source = (GSource*) g_malloc0 (struct_size);
> 
>           source->source_funcs = source_funcs;
> g_malloc0() can fail and return NULL.

Actually, it never will. (See g_try_malloc(), see archives of this list
for plentiful discussion.)

Regards,
						Owen