[PATCH] wayland-util: fix wrap-back of wl_map->free_list when client id >= 0x80000000

[Jason Ekstrand]

Chang,
We cannot change WL_SERVER_ID_START.  I'm not 100% sure why we chose that
value but it's probably because there are significantly more client-side
allocated objects than server-side.  However, at this point, it is fairly
well baked into the protocol and changing it would break backwards
compatibility badly.

And yes, the wl_map structure could stand to be documented better.
--Jason Ekstrand


On Mon, Sep 9, 2013 at 8:10 PM, Chang Liu <cl91tp at gmail.com> wrote:

> Hi Jason,
> Thanks for the review! Indeed, on 32-bit big-endian systems we cannot
> guarentee that the LSB of next and data will coincide. So on these systems
> bumping next to 64 bits might not be a good idea.
>
> I agree that on 32-bit systems this is likely to be a non-issue. Anyway I
> think we should at least document this (somewhat surprising) behaviour in
> the documentation.
>
> Actually since we are going to have this wrap-back behaviour for client
> ids, why don't we just define WL_SERVER_ID_START to be simply 0x80000000?
> Is there any particular reason that we have to choose 0xff000000 for the
> split point of client and server ids? If we don't and current code doesn't
> depend on the precise value of WL_SERVER_ID_START, by simply redefining
> WL_SERVER_ID_START to be 0x80000000 we can be free of wrap-backs of ids and
> have a more symmetric split between client and server ids.
>
> Cheers,
> Chang Liu
> On Sep 9, 2013 11:49 PM, "Jason Ekstrand" <jason at jlekstrand.net> wrote:
>
>> Chang,
>> I think what your doing here may technically be more correct, but I don't
>> like it for two reasons.
>>
>> First, I'm not 100% sure how the unions are going to pack and we heavily
>> use the fact that the bottom bit of the value is for flagging it as unused.
>>  If the next and data fields are different sizes this could cause problems
>> particularly when you consider 32bit vs. 64bit and little vs. bit endian.
>>  I'm not sure that we can guarantee that the bottom bits will still
>> coincide if we simply change it to uint64_t.
>>
>> Second, I think it's a non-issue.  Sure, the protocol theoretically
>> allows a client allocate 0x80000000 objects on a 32-bit system.  However,
>> doing so would create so many wl_resource and wl_proxy objects that both
>> client and server would run out of address space long before we ever hit
>> that mark.  On a 64bit system, uintptr_t is big enough that it's not a
>> problem anyway.
>>
>> Thanks,
>> --Jason Ekstrand
>>
>>
>> On Sun, Sep 8, 2013 at 6:11 AM, Chang Liu <cl91tp at gmail.com> wrote:
>>
>>> The current implementation of wl_map uses uint32_t for free_list.
>>> When removing client id >= 0x80000000, shifting said id by 1 bit left
>>> will cause free_list to wrap back to 0x0. Bump both wl_map->free_list
>>> and union_entry->next to uint64_t to fix this problem.
>>> ---
>>> The relavent lines are:
>>> In wl_map_remove:
>>>         start[i].next = map->free_list;
>>>         map->free_list = (i << 1) | 1;
>>> If we are removing a client id i >= 0x80000000, the MSB of i will be lost
>>> when we perform i << 1, and this causes free_list to wrap back to 0x0.
>>> In wl_map_insert_new:
>>>         if (map->free_list) {
>>>                 entry = &start[map->free_list >> 1];
>>>                 map->free_list = entry->next;
>>>         }
>>> With free_list wrapped back to 0x0, we are longer able to recover the
>>> missing
>>> MSB in the client id even if we perform a right-shift to free_list.
>>>
>>>  src/wayland-private.h | 2 +-
>>>  src/wayland-util.c    | 6 +++---
>>>  2 files changed, 4 insertions(+), 4 deletions(-)
>>>
>>> diff --git a/src/wayland-private.h b/src/wayland-private.h
>>> index 67e8783..5b3715d 100644
>>> --- a/src/wayland-private.h
>>> +++ b/src/wayland-private.h
>>> @@ -63,7 +63,7 @@ struct wl_map {
>>>         struct wl_array client_entries;
>>>         struct wl_array server_entries;
>>>         uint32_t side;
>>> -       uint32_t free_list;
>>> +       uint64_t free_list;
>>>  };
>>>
>>>  typedef void (*wl_iterator_func_t)(void *element, void *data);
>>> diff --git a/src/wayland-util.c b/src/wayland-util.c
>>> index 4fe9c81..1798fd6 100644
>>> --- a/src/wayland-util.c
>>> +++ b/src/wayland-util.c
>>> @@ -149,12 +149,12 @@ wl_array_copy(struct wl_array *array, struct
>>> wl_array *source)
>>>  }
>>>
>>>  union map_entry {
>>> -       uintptr_t next;
>>> +       uint64_t next;
>>>         void *data;
>>>  };
>>>
>>>  #define map_entry_is_free(entry) ((entry).next & 0x1)
>>> -#define map_entry_get_data(entry) ((void *)((entry).next &
>>> ~(uintptr_t)0x3))
>>> +#define map_entry_get_data(entry) ((void *)((entry).next & ~0x3))
>>>  #define map_entry_get_flags(entry) (((entry).next >> 1) & 0x1)
>>>
>>>  WL_EXPORT void
>>> @@ -291,7 +291,7 @@ wl_map_remove(struct wl_map *map, uint32_t i)
>>>
>>>         start = entries->data;
>>>         start[i].next = map->free_list;
>>> -       map->free_list = (i << 1) | 1;
>>> +       map->free_list = ((uint64_t)i << 1) | 1;
>>>  }
>>>
>>>  WL_EXPORT void *
>>> --
>>> 1.8.3.4
>>>
>>> _______________________________________________
>>> wayland-devel mailing list
>>> wayland-devel at lists.freedesktop.org
>>> http://lists.freedesktop.org/mailman/listinfo/wayland-devel
>>>
>>
>>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.freedesktop.org/archives/wayland-devel/attachments/20130910/d91b5384/attachment.html>