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

[Jason Ekstrand]

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/20130909/ba3f6087/attachment.html>